using System.Collections.Generic;
public static void Main() {
var graph = new DirectedGraph(13);
var scc = new StronglyConnectedComponents(graph);
Console.WriteLine(scc.AreStronglyConnected(2, 5));
public static void PopulateGraph(DirectedGraph graph) {
public class StronglyConnectedComponents {
private int[] componentIds;
public int ComponentCount { get; private set; }
public StronglyConnectedComponents(DirectedGraph graph) {
visited = new bool[graph.VertexCount];
componentIds = new int[graph.VertexCount];
var order = new GraphTraversal(graph).ReverseOrder();
var reversedGraph = graph.Reverse();
foreach (var vertex in order) {
DepthFirstSearch(reversedGraph, vertex);
public int VertexComponentId(int vertex) {
return componentIds[vertex];
public bool AreStronglyConnected(int source, int target) {
return componentIds[source] == componentIds[target];
private void DepthFirstSearch(DirectedGraph graph, int vertex) {
componentIds[vertex] = ComponentCount;
foreach (var adjacent in graph.AdjacentTo(vertex)) {
if (!visited[adjacent]) {
DepthFirstSearch(graph, adjacent);
public class GraphTraversal {
private Stack<int> reversePostOrder;
public GraphTraversal(DirectedGraph graph) {
visited = new bool[graph.VertexCount];
reversePostOrder = new Stack<int>();
for (var vertex = 0; vertex < graph.VertexCount; vertex++) {
DepthFirstSearch(graph, vertex);
public IEnumerable<int> ReverseOrder() {
private void DepthFirstSearch(DirectedGraph graph, int vertex) {
foreach (var adjacent in graph.AdjacentTo(vertex)) {
if (!visited[adjacent]) {
DepthFirstSearch(graph, adjacent);
reversePostOrder.Push(vertex);
public class DirectedGraph {
public int VertexCount { get; set; }
public int EdgeCount { get; set; }
private List<int>[] adjacencyLists;
public DirectedGraph(int vertexCount) {
VertexCount = vertexCount;
InitializeAdjacencyLists(vertexCount);
public void AddEdge(int from, int to) {
adjacencyLists[from].Add(to);
public IEnumerable<int> AdjacentTo(int vertex) {
return adjacencyLists[vertex];
public DirectedGraph Reverse() {
var reversedGraph = new DirectedGraph(this.VertexCount);
for (var vertex = 0; vertex < this.VertexCount; vertex++) {
foreach (var adjacent in this.AdjacentTo(vertex)) {
reversedGraph.AddEdge(adjacent, vertex);
public override string ToString() {
String graghString = VertexCount + " vertices, " + EdgeCount + " edges \n";
for (int vertex = 0; vertex < VertexCount; vertex++) {
graghString+= vertex + ": ";
foreach (var adjacnet in this.AdjacentTo(vertex)) {
graghString += adjacnet + " ";
private void InitializeAdjacencyLists(int vertexCount) {
adjacencyLists = new List<int>[vertexCount];
for (var vertex = 0; vertex < vertexCount; vertex++) {
adjacencyLists[vertex] = new List<int>();