The Celebrity Problem | C ++ program to find celebrity ; Max # of persons in the party ; Person with 2 is celebrity ; Returns - 1 if celebrity is not present . If present , returns id ( value from 0 to n - 1 ) . ; the graph needs not be constructed as the edges can be found by using knows function degree array ; ; query for all edges ; set the degrees ; find a person with indegree n - 1 and out degree 0 ; Driver code
#include <bits/stdc++.h> NEW_LINE #include <list> NEW_LINE using namespace std ; #define N  8 NEW_LINE bool MATRIX [ N ] [ N ] = { { 0 , 0 , 1 , 0 } , { 0 , 0 , 1 , 0 } , { 0 , 0 , 0 , 0 } , { 0 , 0 , 1 , 0 } } ; bool knows ( int a , int b ) { return MATRIX [ a ] [ b ] ; } int findCelebrity ( int n ) { int indegree [ n ] = { 0 } , outdegree [ n ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { int x = knows ( i , j ) ; outdegree [ i ] += x ; indegree [ j ] += x ; } } for ( int i = 0 ; i < n ; i ++ ) if ( indegree [ i ] == n - 1 && outdegree [ i ] == 0 ) return i ; return -1 ; } int main ( ) { int n = 4 ; int id = findCelebrity ( n ) ; id == -1 ? cout << " No ▁ celebrity " : cout << " Celebrity ▁ ID ▁ " << id ; return 0 ; }