Naive Approach:

We will count two things about any person, first how many people (s)he knows in the party(out) and second how many people know that person(in). We will store these values for every person and according to the problem, celebrity does not know anybody at the party but everybody knows h(im/er). So, we need to find a specific pair of values in the data we stored earlier, celebrity does not know anybody means it will have `0` for how many people he/she know value and everybody knows celebrity so it will have `n-1` for how many people know that person value, everybody knows except itself so, no. of people - 1(n-1).

Pseudo Code

function getId(givenMatrix, ) {
  Create two arrays in and out of size N and initialize all value with 0
  // in is for how many people know that person
  // out is for how many people he/she knows
  Traverse the whole matrix:
    Run nested loops outer from 0 to N and inner from 0 to N
    //inner loop for "in" and outer loop for "out" array
    For every value in matrix add the value to both array with respect to its iterator
  Traverse both array at same time and check for the pair in[x] = (N-1) && out[x] = 0
    If found:
      return x
    If not found:
      return -1

C++ Function Implementation

int getId(int M[MAX][MAX], int n)
{
    int in[n]={0},out[n]={0};

    for(int i=0; i < n; i++)
    {
        for(int j=0; j < n; j++)
        {
            int x = M[i][j];

            out[i]+=x;
            in[j]+=x;
        }
    }

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

    return -1;
}

Optimised Approach

It is a two pointer approach one will start from beginning and other will start from end. Let beginning pointer be `a` and end pointer be `b`.
we will check if `a` knows `b`, if yes then `a` must not be celebrity else `b` must not be celebrity
At the end of traversal assign `a` as celebrity index.
Again check again if this person is celebrity or not if yes then return `a` else return `-1`
We will check this by counting number of people this person knows and number of people who know this person.

Pseudo Code

function getId() {
  Create two variable for a and b and initialize them as a = 0 and b = n - 1
  Run a loop while a < b:
    If a knows b:
      increment a
    Else:
      decrement b
  set a as celebrity
  Run a loop from 0 to n-1 and count no. of people this person knows
  and no. of people who know this person
    IF No. of people this person knows is 0 and No. of people who know this person is n-1:
      return a
    Else:
      return -1

C++ Function Implementation

int getId(int M[MAX][MAX], int n)
{
    int a = 0;
    int b = n - 1;

    while (a < b)
    {
        if (M[a][b]){
            a++;
        }
        else{
            b--;
		}
    }

    for (int i = 0; i < n; i++) {

        if ( (i != a) && (M[a][i] || !M[i][a]) ){
            return -1;
        }
    }

    return a;
}

Program Code

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

//---------------Naive Approach----------------
/*
int getId(int M[MAX][MAX], int n)
{
    int in[n]={0},out[n]={0};

    for(int i=0; i < n; i++)
    {
        for(int j=0; j < n; j++)
        {
            int x = M[i][j];

            out[i]+=x;
            in[j]+=x;
        }
    }

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

    return -1;
}*/

//------------------Optimised Approach-----------------
int getId(int M[MAX][MAX], int n)
{
    int a = 0;
    int b = n - 1;

    while (a < b)
    {
        if (M[a][b]){
            a++;
        }
        else{
            b--;
		}
    }

    for (int i = 0; i < n; i++) {

        if ( (i != a) && (M[a][i] || !M[i][a]) ){
            return -1;
        }
    }

    return a;
}

int main()
{
    int T;
    cin >> T;
    int M[MAX][MAX];
    while(T--)
    {
        int N;
        cin >> N;
        memset(M,0,sizeof M);
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                cin >> M[i][j];
            }
        }
        cout << getId(M,N) << endl;

    }
}