博客

转载自http://poplars.blog.163.com/blog/static/139422174201085113427209/

　　在n个人中，有一个被所有人知道但却不知道别人的人，这个人被定义为社会名流。现在的问题是如果存在，试找出社会名流。你可以使用的唯一方式是询问：“对不起，请问你知道某某人吗？”。由于有n(n-1)/2对人，如果提问是随意的，那么问题的规模是n(n-1)。

抽象地来说，社会名流问题可以被表示为图论问题。使用一个有向图，每个顶点表示一个人，如果A知道B，则从A到B有一条边。一个社会名流对应于图中的汇点。一个汇点是入度为n-1而出度为0的顶点。

输入：nxn的连结矩阵M(如果i知道j，则M[i][j] == true)

输出：社会名流

 

　　解法的关键在于如何减小问题的规模，把n降为n-1，而不是将n-1归纳到n。可以尝试用数学归纳法来分析这个问题，归纳假设：已知如何从n-1个人中找出社会名流。这里归纳次序很重要，不要从n-1扩展到n来求解问题，而仅仅是利用归纳假设来减小问题的规模，当无元素可消除的时候，算法也就结束了。

　　具体做法如下：我们问A是否知道B，如果A知道B则A不可能是社会名流，反之则B不是社会名流。这样我们肯定可以通过一个问题来删除其中之一，从而问题规模减小到n-1，根据归纳假设我们知道如何在n-1中找到社会名流。每次询问可以排除一个候选，如果我们一直减小问题规模，最后只会有一个候选人留下，此时我们再回过头来检查这个候选人是否合法。问题输入的规模为n平方，算法复杂度为O(n)

 

size_t size = input.size();

size_t i=0,j=1;

while(j < size)

{

　　if (input[i][j] == true) //i–>j，i不是社会名流

　　{

　　　　i = j; //j成为候选

　　} //否则舍弃j

　　++j; //测试下一人

}

int candidate = i;// i是社会名流的唯一候选

//检验i是否符合社会名流

size_t k;

for (k=0; k < size; ++k)

{

　　if (k == candidate) {continue;}

　　if (!(input[k][candidate] == true || input[candidate][k] == false)) //k不认识i或i认识k，则不符合条件

　　　　break;

}

return (k == size) ? candidate : -1;