P2419题解

一种不是拓扑排序也不是Floyd的玄学算法

目的

就拿样例来说吧：

我们其实可以从图中获得更多信息，比如1比5厉害等，所以我们希望它能把我们所有的已知信息都表现出来，像这样：

然后就可以方便地做判断了：哪个点的入度和出度之和 $=n-1$ ，哪个点就可以确定排名。
在实际应用中，我们为了方便，再把每个点都和自己连一条边（反正不用任何图论算法，连了也没关系），就可以直接判断哪个点的入度和出度之和 $=n$ 了。

具体方法

先用矩阵存图，1指向2就把第一行第二列变成1，以此类推，得到：

然后要变成第二张图的样子（把所有已知信息表示出来），具体步骤：
如果$(x,y)$点有标记，$(y,z)$点也有标记，那么$(x,z)$点就可以打标记。

为什么呢？因为$(x,y)$点有标记表示$x$比$y$厉害，$(y,z)$点有标记表示$y$比$z$厉害，$x$比$y$厉害，$y$比$z$厉害，$x$就比$z$厉害，所以$(x,z)$点就可以打标记。

最后，要如何判断点i能否和每个点都连边呢？其实很简单：只需要把第i行和第i列上的点都加起来，再减去1（点$(i,i)$被计算了两次），看是否为n就行。

为什么呢？因为第$i$行的标记表示$i$比别“人”厉害，第$i$列的标记表示别“人”比$i$厉害，知道几个“人”比$i$厉害，几个“人”比$i$蒻，就可以知道i的排名了。

算法比较难理解，有耐心的话可以仔细画画想想。

---

附上AC代码：

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast")
#pragma GCC optimize("inline")
using namespace std;
bool a[110][110];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x][y]=1;
	}
	for(int i=1;i<=n;i++)
		a[i][i]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i][j])
			{
				for(int k=1;k<=n;k++)
					if(k!=i&&a[k][i])
						a[k][j]=1;
				for(int k=1;k<=n;k++)
					if(k!=j&&a[j][k])
						a[i][k]=1;
			}
	int num=0;
	for(int i=1;i<=n;i++)
	{
		int ans=0;
		for(int j=1;j<=n;j++)
		{
			ans+=a[i][j];
			ans+=a[j][i];
		}
		if(ans-1==n)
			num++;
	}
	cout<<num<<endl;
	return 0;
}