LeetCode #207 - Course Schedule

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Graph {
private:
    unordered_map<int, vector<int>> adjList;

public:
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
    }

    bool hasCycle() {
        unordered_set<int> visited;
        unordered_set<int> recStack;

        for (auto& pair : adjList) {
            int node = pair.first;
            if (visited.find(node) == visited.end()) {
                if (hasCycleUtil(node, visited, recStack)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    bool hasCycleUtil(int node, unordered_set<int>& visited, unordered_set<int>& recStack) {
        visited.insert(node);
        recStack.insert(node);

        for (int neighbor : adjList[node]) {
            if (visited.find(neighbor) == visited.end()) {
                if (hasCycleUtil(neighbor, visited, recStack)) {
                    return true;
                }
            } else if (recStack.find(neighbor) != recStack.end()) {
                return true;
            }
        }

        recStack.erase(node);
        return false;
    }
};

int main() {
    Graph g;
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 0); // This creates a cycle
    cout << (g.hasCycle() ? "true" : "false") << endl;
    return 0;
}

package main

import (
    "fmt"
    "github.com/chebyrash/graph"
)

type Graph struct {
    adjList map[int][]int
}

func NewGraph() *Graph {
    return &Graph{adjList: make(map[int][]int)}
}

func (g *Graph) AddEdge(u, v int) {
    g.adjList[u] = append(g.adjList[u], v)
}

func (g *Graph) HasCycle() bool {
    visited := make(map[int]bool)
    recStack := make(map[int]bool)

    for node := range g.adjList {
        if !visited[node] {
            if g.hasCycleUtil(node, visited, recStack) {
                return true
            }
        }
    }
    return false
}

func (g *Graph) hasCycleUtil(node int, visited, recStack map[int]bool) bool {
    visited[node] = true
    recStack[node] = true

    for _, neighbor := range g.adjList[node] {
        if !visited[neighbor] {
            if g.hasCycleUtil(neighbor, visited, recStack) {
                return true
            }
        } else if recStack[neighbor] {
            return true
        }
    }

    recStack[node] = false
    return false
}

func main() {
    g := NewGraph()
    g.AddEdge(0, 1)
    g.AddEdge(1, 2)
    g.AddEdge(2, 0) // This creates a cycle
    fmt.Println(g.HasCycle())
}

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph() {
        adjList = new HashMap<>();
    }

    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
    }

    public boolean hasCycle() {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> recStack = new HashSet<>();

        for (int node : adjList.keySet()) {
            if (!visited.contains(node)) {
                if (hasCycleUtil(node, visited, recStack)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean hasCycleUtil(int node, Set<Integer> visited, Set<Integer> recStack) {
        visited.add(node);
        recStack.add(node);

        for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                if (hasCycleUtil(neighbor, visited, recStack)) {
                    return true;
                }
            } else if (recStack.contains(neighbor)) {
                return true;
            }
        }

        recStack.remove(node);
        return false;
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 0); // This creates a cycle
        System.out.println(g.hasCycle());
    }
}

class Graph {
    constructor() {
        this.adjList = new Map();
    }

    addEdge(u, v) {
        if (!this.adjList.has(u)) this.adjList.set(u, []);
        this.adjList.get(u).push(v);
    }

    hasCycle() {
        const visited = new Set();
        const recStack = new Set();

        for (let node of this.adjList.keys()) {
            if (!visited.has(node)) {
                if (this.hasCycleUtil(node, visited, recStack)) {
                    return true;
                }
            }
        }
        return false;
    }

    hasCycleUtil(node, visited, recStack) {
        visited.add(node);
        recStack.add(node);

        for (let neighbor of this.adjList.get(node) || []) {
            if (!visited.has(neighbor)) {
                if (this.hasCycleUtil(neighbor, visited, recStack)) {
                    return true;
                }
            } else if (recStack.has(neighbor)) {
                return true;
            }
        }

        recStack.delete(node);
        return false;
    }
}

// Example Usage
const g = new Graph();
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0); // This creates a cycle
console.log(g.hasCycle());

<?php
class Graph {
    private $adjList;

    public function __construct() {
        $this->adjList = [];
    }

    public function addEdge($u, $v) {
        if (!isset($this->adjList[$u])) {
            $this->adjList[$u] = [];
        }
        $this->adjList[$u][] = $v;
    }

    public function hasCycle() {
        $visited = [];
        $recStack = [];

        foreach (array_keys($this->adjList) as $node) {
            if (!isset($visited[$node])) {
                if ($this->hasCycleUtil($node, $visited, $recStack)) {
                    return true;
                }
            }
        }
        return false;
    }

    private function hasCycleUtil($node, &$visited, &$recStack) {
        $visited[$node] = true;
        $recStack[$node] = true;

        foreach ($this->adjList[$node] ?? [] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                if ($this->hasCycleUtil($neighbor, $visited, $recStack)) {
                    return true;
                }
            } elseif (isset($recStack[$neighbor])) {
                return true;
            }
        }

        unset($recStack[$node]);
        return false;
    }
}

// Example Usage
$g = new Graph();
$g->addEdge(0, 1);
$g->addEdge(1, 2);
$g->addEdge(2, 0); // This creates a cycle
echo $g->hasCycle() ? 'true' : 'false';
?>

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def has_cycle(self):
        visited = set()
        rec_stack = set()

        for node in self.graph:
            if node not in visited:
                if self._has_cycle_util(node, visited, rec_stack):
                    return True
        return False

    def _has_cycle_util(self, node, visited, rec_stack):
        visited.add(node)
        rec_stack.add(node)

        for neighbor in self.graph[node]:
            if neighbor not in visited:
                if self._has_cycle_util(neighbor, visited, rec_stack):
                    return True
            elif neighbor in rec_stack:
                return True

        rec_stack.remove(node)
        return False

# Example Usage
if __name__ == '__main__':
    g = Graph()
    g.add_edge(0, 1)
    g.add_edge(1, 2)
    g.add_edge(2, 0)  # This creates a cycle
    print(g.has_cycle())