社会名流问题

社会名流问题:

给定一个n×n邻接矩阵,确定是否存在一个i,
其满足在第i列所有项(除了第ii项)都为1,并
且第i行所有项(除了第ii项)都为0。

 

插话:这个其实就是有向图求源与汇的变形,O(n)算法非常经典,也是先找出一个来,如果有源肯定是该元素,该元素如果不是源,则就没有社会名流了

大致的算法思路:

随便取一个非对角线元素,比如Array[i][j],如果Array[i][j]=0成立,则j不是社会名流,于是删去第j行和第j列。

同样,如果Array[i][j]=1成立,则删去第i行和第i列;

总之,无论对应项取何值,都可以删去一行和一列,因此整个操作只耗费O(n)的时间。

重复此操作直至剩下最后一个元素。

最后,检验该元素是否为社会名流即可。

如果该元素不是,则该群人中不存在社会名流。

原文地址:https://www.cnblogs.com/warmfrog/p/3652756.html