Cpp_prep/Celebrityproblembystack.cpp at main · urvashiparashar/Cpp_prep · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// { Driver Code Starts
//Initial template for C++

#include<bits/stdc++.h>
using namespace std;

 // } Driver Code Ends
//User function template for C++

class Solution
{
    public:

    //function to find if every one knows everyone or not
    bool knows(vector<vector<int> >& M,int a,int b,int n)
    {
        if(M[a][b]==1)
        {
            return true;
        }
        else
        {
            return false;
        }

    }


    //Function to find if there is a celebrity in the party or not.
    int celebrity(vector<vector<int> >& M, int n)
    {
        // code here
        stack<int>s;
        //push all elements into stack
        for(int i=0;i<n;i++)
        {
            s.push(i);
        }
        //step2: perform till stack size is 1
        while(s.size()>1)
        {
            int a=s.top();
            s.pop(); //for pushing and popping to see if it is 0 and 1 i.e knows or not knows
            int b=s.top();
            s.pop();
            if(knows(M,a,b,n))
            {
                //if a knows b then push b and discard a
                s.push(b);
            }
            else
            {
                s.push(a); //else push a
            }
        }
        int cand=s.top();
        //step 3: to find if ele is potential or not
        //checking for rows
        bool rowcheck=false;
        int zerocount=0; ///celebrity row must be zero
        for(int i=0;i<n;i++)
        {
            if(M[cand][i]==0)
            {
                zerocount++;
            }
        }
        if(zerocount==n)
        {
            rowcheck=true; //all row value are 0
        }
        //checking for rows
        bool colcheck=false;
        int onecount=0; ///celebrity row must be zero
        for(int i=0;i<n;i++)
        {
            if(M[i][cand]==1)
            {
                onecount++;
            }
        }
        if(onecount==n-1) //except the diagonal element that would be 0
        {
            colcheck=true; //all row value are 0
        }
        if(rowcheck==true && colcheck==true)
        {
            return cand;
        }
        else
        {
            return -1;
        }
    }


};

// { Driver Code Starts.

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<vector<int> > M( n , vector<int> (n, 0));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>M[i][j];
            }
        }
        Solution ob;
        cout<<ob.celebrity(M,n)<<endl;

    }
}
  // } Driver Code Ends