// The vertex v of oriented graph is called ultimate sink if it has no outgoing edges

// and every other vertex has an edge leading to v. 

// Write a program that takes adjacency matrix of the oriented graph and prints the index of ultimate sink vertex

// (or “No ultimate sink” in case there isn’t one). 

// The program should spend O(V) time where V is number of vertices.

using System;

public class Program

{

    public static int UltimateSink(bool [,] m, int V)

    {

        int candidate = 0;

        // invariant: 0<=candidate<=vertex<V and

        //            no vertex v!=candidate in range 0..vertex-1 can be an ultimate sink

        for(int vertex = 1; vertex < V; vertex++)

        {

            if(!m[vertex, candidate]) // then candidate is definitely NOT an ultimate sink

                candidate = vertex;

        }

        // now check the candidate according to definition

        for(int vertex = 0; vertex < V; vertex++)

        {

            if(vertex!=candidate)

            {

                if(m[candidate, vertex] || !m[vertex,candidate]) 

                    return -1;

            }

        }

        return candidate;

    }

​

    public static void Main()

    {

        bool [,] m1 = new bool[4,4] 

        {

            {true,   true,  true, true},

            {true,   true,  true, true},

            {true,   true,  true, true},

            {false, false, false, true}

        };

        Test("m1", m1, 4);

​

        bool [,] m2 = new bool[4,4] 

        {

            {true,  false,  true, false},

            {true,   true,  true, true},

            {true,   true,  true, true},

            {false, false, false, true}

        };

        Test("m2", m2, 4);

​

        bool [,] m3 = new bool[4,4] 

        {

            {true,   true,  true, false},

            {false,  true,  false, false},

            {true,   true,  true, true},

            {true,   true, false, true}

        };

        Test("m3", m3, 4);

​

        Test("1x1 with 0s", new bool[1,1] {{false}}, 1);

        Test("1x1 with 1s", new bool[1,1] {{true}}, 1);

        Test("2x2 with 0s", new bool[2,2] {{false, false}, {false, false}}, 2);

        Test("2x2 with 1s", new bool[2,2] {{true, true}, {true, true}}, 2);

    }

    private static void Test(string test, bool [,] m, int V)

    {

        int sink = UltimateSink(m, V);

        if(sink >= 0)

        {

            Console.WriteLine("Test {0}: vertex {1} is an ultimate sink", test, sink);

        }

        else

        {

            Console.WriteLine("Test {0}: no ultimate sink", test);

        }

    }

}