CSE2202-Algorithm-Design-and-Analysis/Celebrity_Problem.cpp at main · alamgir-ahosain/CSE2202-Algorithm-Design-and-Analysis · 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
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, val;
    cin >> n >> val;
    int v[n][n];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> v[i][j];
        }
    }

    if (val == 1)
    {
        // Graph
        //  Time Complexity-0(n2) space Complexity-0(1)
        int in[n] = {0};
        int out[n] = {0};
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {

                if (v[i][j] == 1)
                {
                    in[j]++;
                    out[i]++;
                }
            }
        }
        int ans = -1;
        for (int i = 0; i < n; i++)
        {
            if (in[i] == n - 1 && out[i] == 0)
            {
                ans = i;
                break;
            }
        }

        cout << ans;
    }
    else if (val == 2)
    {
        // Time Complexity-0(n) space Complexity-0(1)

        int c = 0, f = 0, ans;
        for (int i = 1; i < n; i++)
        {
            if (v[c][i] == 1)
                c = i;
        }
        for (int i = 0; i < n; i++)
        {
            if (i != c && (v[c][i] || v[i][c] == 0))
            {
                f = 1;
                break;
            }
        }
        if (f)
            cout << -1;
        else
            cout << c;
    }

    else if (val == 3)
    {

        // using stack
        stack<int> s;
        for (int i = 0; i < n; i++)
            s.push(i);
        while (s.size() >= 2)
        {
            int i = s.top();
            s.pop();
            int j = s.top();
            s.pop();

            if (v[i][j] == 1)
            {
                // if i knows j -> j is a celebrity
                s.push(j);
            }
            else
                s.push(i);
            // if j knows i -> i is  a celebrity
        }
        int maybe = s.top(), f = 0;
        // cout << maybe << endl;
        for (int i = 0; i < n; i++)
        {
            if (i != maybe)
            {
                if (v[i][maybe] == 0 || v[maybe][i] == 1)
                {
                    f = 1;
                    break;
                }
            }
        }
        if (f)
            cout << "Not Celebrity";
        else
            cout << maybe;
    }
}