using System;

using System.Collections.Generic;

​

public class Program

{

    public static void Main()

    {

        //This implementation borrowed from http://www.introprogramming.info/tag/graph-implementation/

        GraphComponents.Main();

    }

}

​

class GraphComponents

{

    static Graph graph = new Graph(new List<int>[] {

        new List<int>() {4},     // successors of vertice 0

        new List<int>() {1, 2, 6}, // successors of vertice 1

        new List<int>() {1, 6},    // successors of vertice 2

        new List<int>() {6},     // successors of vertice 3

        new List<int>() {0},     // successors of vertice 4

        new List<int>() {},      // successors of vertice 5

        new List<int>() {1, 2, 3}  // successors of vertice 6

    });

    static bool[] visited = new bool[graph.Size];

    public static void TraverseDFS(int v)

    {

        if (!visited[v])

        {

            Console.WriteLine(v + " ");

            visited[v] = true;

            foreach (int child in graph.GetSuccessors(v))

            {

                TraverseDFS(child);

            }

        }

    }

​

    public static void Main()

    {

        graph.AddEdge(1, 3);

        graph.RemoveEdge(1, 2);

        Console.WriteLine("Connected graph components: ");

        for (int v = 0; v < graph.Size; v++)

        {

            if (!visited[v])

            {

                //Console.WriteLine("Calling TraverseDFS() from Main");

                TraverseDFS(v);

            }

        }

    }

}

​

/// <summary>Represents a directed unweighted graph structure

/// </summary>

public class Graph

{

    private List<int>[] childNodes; // this is the adjaceny list, an array of List<int>

    public Graph(int size)

    {

        this.childNodes = new List<int>[size];

        for (int i = 0; i < size; i++)

        {

            this.childNodes[i] = new List<int>();

        }

    }

​

    public Graph(List<int>[] childNodes)

    {

        this.childNodes = childNodes;

    }

​

    public int Size

    {

        get

        {

            return this.childNodes.Length;

        }

    }

​

    public void AddEdge(int u, int v)

    {

        childNodes[u].Add(v);

    }

​

    public void RemoveEdge(int u, int v)

    {

        childNodes[u].Remove(v);

    }

​

    public bool HasEdge(int u, int v)

    {

        bool hasEdge = childNodes[u].Contains(v);

        return hasEdge;

    }

​

    public IList<int> GetSuccessors(int v)

    {

        return childNodes[v];

    }

}