Graph Theory - LeetCode Exercises

A collection of graph algorithm implementations in C# (.NET 9.0), focusing on fundamental graph theory concepts and problem-solving techniques.

Problems

Problem	Algorithm	Time Complexity	Space Complexity
Number of Provinces (LeetCode 547)	Depth-First Search (DFS)	O(n²)	O(n)
Find Eventual Safe Nodes (LeetCode 802)	DFS with State Tracking	O(V + E)	O(V)

Algorithms Implemented

1. Number of Provinces (graf01)

Identifies the number of connected components in an undirected graph represented by an adjacency matrix. Uses DFS to traverse and mark connected vertices, counting distinct provinces.

Key Concept: Connected components in an undirected graph.

2. Find Eventual Safe Nodes (graf02)

Determines which nodes in a directed graph eventually lead to terminal nodes without encountering cycles. Employs DFS with a three-state system (unvisited, visiting, safe) to detect cycles.

Key Concept: Cycle detection in directed graphs.

Building and Running

Each solution is a standalone C# console application.

# Navigate to a problem directory
cd graf01

# Build and run
dotnet run

Requirements

• .NET 9.0 SDK or later

References

• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Graph traversal algorithms: DFS, cycle detection, connected components