The Celebrity Problem

using System;
using System.Collections.Generic;

public class MainClass {
    public static int Celebrity(List<List<int> > M, int n)
    {
        List<int>[] adj = new List<int>[ n ];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
            for (int j = 0; j < n; j++) {
                if (M[i][j] == 1) {
                    adj[i].Add(j);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (adj[i].Count == 0) {
                bool flag = true;
                for (int j = 0; j < n; j++) {
                    if (i == j)
                        continue;
                    if (!adj[j].Contains(i)) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    return i;
            }
        }
        return -1;
    }

    public static void Main(string[] args)
    {
        List<List<int> > M = new List<List<int> >{
            new List<int>{ 0, 0, 1, 0 },
            new List<int>{ 0, 0, 1, 0 },
            new List<int>{ 0, 0, 0, 0 },
            new List<int>{ 0, 0, 1, 0 }
        };
        int n = M.Count;
        int CelebrityResult = Celebrity(M, n);

        if (CelebrityResult != -1) {
            Console.WriteLine("Celebrity is : "
                              + CelebrityResult);
        }
        else {
            Console.WriteLine("No celebrity");
        }
    }
}

// C# program to find celebrity

using System;
public class GFG {

    // Max # of persons in the party
    static readonly int N = 8;

    // Person with 2 is celebrity
    static int[, ] MATRIX = { { 0, 0, 1, 0 },
                              { 0, 0, 1, 0 },
                              { 0, 0, 0, 0 },
                              { 0, 0, 1, 0 } };

    static int knows(int a, int b) { return MATRIX[a, b]; }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    static int findCelebrity(int n)
    {

        // the graph needs not be constructed
        // as the edges can be found by
        // using knows function

        // degree array;
        int[] indegree = new int[n];
        int[] outdegree = new int[n];

        // query for all edges
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int x = knows(i, j);

                // set the degrees
                outdegree[i] += x;
                indegree[j] += x;
            }
        }

        // find a person with indegree n-1
        // and out degree 0
        for (int i = 0; i < n; i++)
            if (indegree[i] == n - 1 && outdegree[i] == 0)
                return i;

        return -1;
    }

    // Driver code
    public static void Main(String[] args)
    {
        int n = 4;
        int id = findCelebrity(n);
        if (id == -1)
            Console.Write("No celebrity");
        else
            Console.Write("Celebrity ID " + id);
    }
}

// This code is contributed by aashish1995

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {

    // Max # of persons in the party
    static int N = 8;

    // Person with 2 is celebrity
    static int[, ] MATRIX = { { 0, 0, 1, 0 },
                              { 0, 0, 1, 0 },
                              { 0, 0, 0, 0 },
                              { 0, 0, 1, 0 } };

    static int knows(int a, int b) { return MATRIX[a, b]; }

    // Returns -1 if a 'potential celebrity'
    // is not present. If present,
    // returns id (value from 0 to n-1).
    static int findPotentialCelebrity(int n)
    {

        // base case - when n reaches 0 , returns -1
        // since n represents the number of people,
        // 0 people implies no celebrity(= -1)
        if (n == 0)
            return -1;

        // find the celebrity with n-1
        // persons
        int id = findPotentialCelebrity(n - 1);

        // if there are no celebrities
        if (id == -1)
            return n - 1;

        // if the id knows the nth person
        // then the id cannot be a celebrity, but nth person
        // could be one
        else if (knows(id, n - 1) == 1) {
            return n - 1;
        }

        // if the nth person knows the id,
        // then the nth person cannot be a celebrity and the
        // id could be one
        else if (knows(n - 1, id) == 1) {
            return id;
        }

        // if there is no celebrity
        return -1;
    }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    // a wrapper over findCelebrity
    static int Celebrity(int n)
    {

        // find the celebrity
        int id = findPotentialCelebrity(n);

        // check if the celebrity found
        // is really the celebrity
        if (id == -1)
            return id;
        else {
            int c1 = 0, c2 = 0;

            // check the id is really the
            // celebrity
            for (int i = 0; i < n; i++)
                if (i != id) {
                    c1 += knows(id, i);
                    c2 += knows(i, id);
                }

            // if the person is known to
            // everyone.
            if (c1 == 0 && c2 == n - 1)
                return id;

            return -1;
        }
    }

    // Driver code
    public static void Main(String[] args)
    {
        int n = 4;
        int id = Celebrity(n);
        if (id == -1) {
            Console.WriteLine("No celebrity");
        }
        else {
            Console.WriteLine("Celebrity ID " + id);
        }
    }
}

// This code is contributed by gauravrajput1

// C# program to find celebrity using
// stack data structure
using System;
using System.Collections.Generic;

public class GFG {
    // Person with 2 is celebrity
    static int[, ] MATRIX = { { 0, 0, 1, 0 },
                              { 0, 0, 1, 0 },
                              { 0, 0, 0, 0 },
                              { 0, 0, 1, 0 } };

    // Returns true if a knows
    // b, false otherwise
    static bool knows(int a, int b)
    {
        bool res = (MATRIX[a, b] == 1) ? true : false;
        return res;
    }

    // Returns -1 if celebrity
    // is not present. If present,
    // returns id (value from 0 to n-1).
    static int findCelebrity(int n)
    {
        Stack<int> st = new Stack<int>();
        int c;

        // Step 1 :Push everybody
        // onto stack
        for (int i = 0; i < n; i++) {
            st.Push(i);
        }

        while (st.Count > 1) {
            // Step 2 :Pop off top
            // two persons from the
            // stack, discard one
            // person based on return
            // status of knows(A, B).
            int a = st.Pop();
            int b = st.Pop();

            // Step 3 : Push the
            // remained person onto stack.
            if (knows(a, b)) {
                st.Push(b);
            }

            else
                st.Push(a);
        }

        // If there are only two people
        // and there is no
        // potential candidate
        if (st.Count == 0)
            return -1;

        c = st.Pop();

        // Step 5 : Check if the last
        // person is celebrity or not
        for (int i = 0; i < n; i++) {
            // If any person doesn't
            //  know 'c' or 'a' doesn't
            // know any person, return -1
            if (i != c && (knows(c, i) || !knows(i, c)))
                return -1;
        }
        return c;
    }

    // Driver Code
    public static void Main(String[] args)
    {
        int n = 4;
        int result = findCelebrity(n);
        if (result == -1) {
            Console.WriteLine("No Celebrity");
        }
        else
            Console.WriteLine("Celebrity ID " + result);
    }
}

// This code is contributed by umadevi9616