using System;

using System.Collections.Generic;

​

public class Program

{

    public class Graph

    {

        private int[,] adjMatrix;

​

        public Graph(int vertices)

        {

            adjMatrix = new int[vertices, vertices];

        }

​

        public int[,] AdjMatrix

        {

            get

            {

                return adjMatrix;

            }

        }

​

        public void AddEdge(int source, int destination)

        {

            adjMatrix[source, destination] = 1;

            adjMatrix[destination, source] = 1;

        }

    }

​

    public static HashSet<Tuple<int, int>> Bridges(Graph graph)

    {

        var visited = new HashSet<int>();

        var bridges = new HashSet<Tuple<int, int>>();

        var ids = new Dictionary<int, int>();

        var lowLinkValues = new Dictionary<int, int>();

        var parent = -1;

        var id = 0;

​

        for (int i = 0; i < graph.AdjMatrix.GetLength(0); i++)

        {

            if (visited.Contains(i))

            {

                continue;

            }

​

            Dfs(i, parent, id, bridges, ids, lowLinkValues, visited, graph.AdjMatrix);

        }

​

        return bridges;

    }

    private static void Dfs(

        int vertex,

        int parent,

        int id,

        HashSet<Tuple<int, int>> bridges,

        Dictionary<int, int> ids,

        Dictionary<int, int> lowLinkValues,

        HashSet<int> visited,

        int[,] adjMatrix)

    {

        visited.Add(vertex);

        ids.Add(vertex, id);

        lowLinkValues.Add(vertex, id);

        id++;

​

        for (int i = 0; i < adjMatrix.GetLength(0); i++)

        {

            if (parent == i)

            {

                continue;

            }

​

            if (!visited.Contains(i))

            {

                parent = vertex;

                Dfs(i, parent, id, bridges, ids, lowLinkValues, visited, adjMatrix);

​

                if (ids[vertex] < lowLinkValues[i])

                {

                    bridges.Add(Tuple.Create(vertex, i));

                }

                else

                {

                    lowLinkValues[vertex] = Math.Min(lowLinkValues[vertex], lowLinkValues[i]);

                }

            }

            else

            {

                lowLinkValues[vertex] = Math.Min(lowLinkValues[vertex], ids[i]);

            }

        }

    }

​

    public static void Main()

    {

        // Adjacency Matrix:

        var g = new Graph(11);

​

        g.AddEdge(0, 1);

        g.AddEdge(0, 2);

        g.AddEdge(0, 3);

        g.AddEdge(0, 4);

        g.AddEdge(4, 2);

        g.AddEdge(3, 5);

        g.AddEdge(4, 6);

        g.AddEdge(6, 3);

        g.AddEdge(6, 7);

        g.AddEdge(6, 8);

        g.AddEdge(7, 9);

        g.AddEdge(9, 10);

        g.AddEdge(8, 10);

        // bridges should be: 0--1, 3--5

        // but bridges collection is empty

        var bridges = Bridges(g);

        foreach (var bridge in bridges)

        {

            Console.WriteLine(bridge.Item1);

            Console.WriteLine(bridge.Item2);

            Console.WriteLine("\n");

        }

    }

}

​