LeetCode 277. 搜寻名人（思维题）

输入: graph = [
  [1,1,0],
  [0,1,0],
  [1,1,1]
]
输出: 1
解析: 有编号分别为 0、1 和 2 的三个人。
graph[i][j] = 1 代表编号为 i 的人认识编号为 j 的人，
而 graph[i][j] = 0 则代表编号为 i 的人不认识编号为 j 的人。
“名人” 是编号 1 的人，因为 0 和 2 均认识他/她，但 1 不认识任何人。

输入: graph = [
  [1,0,1],
  [1,1,0],
  [0,1,1]
]
输出: -1
解析: 没有 “名人”
 
注意:
该有向图是以邻接矩阵的形式给出的，是一个 n × n 的矩阵， 
a[i][j] = 1 代表 i 与 j 认识，a[i][j] = 0 则代表 i 与 j 不认识。
请记住，您是无法直接访问邻接矩阵的。

/* The knows API is defined for you.
      bool knows(int a, int b); */

class Solution {
public:
    int findCelebrity(int n) {
        int i, j, count, ans = -1;
        bool famous;
        for(i = 0; i < n; ++i)
        {
        	famous = true;
        	count = 1;//自己认识自己
        	for(j = 0; j < n; ++j)
        	{
        		if(i == j)
        			continue;
        		if(knows(j, i))//j 认识 i
        			count++;
        		if(count < j+1)//有人不认识 i
        			break;//不是名人
        		if(knows(i,j))//他还认识别人,不是名人
        		{
        			famous = false;
        			break;
        		}
        	}
        	if(famous && count == n)//都认识他
        	{
        		ans = i;
        		break;
        	}
        }
        return ans;
    }
};

class Solution {
public:
    int findCelebrity(int n) {
    	int ans = 0;
        for(int i = 1; i < n; ++i)
        {
        	if(knows(ans, i))//认识i,ans不是名人
        		ans = i;
        }
        for(int i = 0; i < n; ++i)
        {
        	if(ans == i) continue;
        	if(knows(ans, i) || !knows(i, ans))//认识别人或者有人不认识他
        		return -1;
        }
        return ans;
    }
};