Celebrity Problem, O(n^2) and O(n)

celebrity.cc

#include <iostream>
#include <list>

using namespace std;

#define N 4
int size = N;
bool MATRIX[N][N] = {
	{0, 1, 1, 1},
	{0, 0, 1, 1},
	{0, 0, 0, 1},
	{0, 0, 1, 0}
};

bool KnowHim(int a, int b) { return MATRIX[a][b]; }

// O(n^2)
int celebrity() {
	for (int i = 0; i < size; ++i) {
		int somebody_knows = 0;
		for (int j = 0; j < size; ++j) {
			somebody_knows |= KnowHim(i, j);
		}
		if (somebody_knows == 0) {
			int j;
			for (j = 0; j < size; ++j) {
				if (i == j) continue;
				if (!KnowHim(j, i)) break;
			}
			if (j == size)
				return i;
		}
	}
	return -1;
}

// O(n)
int celebrity2() {
	list<int> s;

	for (int i = 0; i < size; ++i)
		s.push_back(i);

	for (; s.size() > 1;) {
		int a = s.back();
		s.pop_back();
		int b = s.back();
		s.pop_back();

		bool f1 = KnowHim(a, b);
		bool f2 = KnowHim(b, a);

		if (f1 && f2) continue;
		if (f1) s.push_front(b);
		if (f2) s.push_front(a);
	}

	int r = s.back();
	for (int i = 0; i < size; ++i) {
		if (i == r) continue;
		if ( KnowHim(r, i)) return -1;
		if (!KnowHim(i, r)) return -1;
	}

    return r;
}


int main(int argc, char **argv) {

	cout << celebrity() << endl;
	cout << celebrity2() << endl;

	return 0;
}