Popular Cows_牛客博客

Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.

Input

* Line 1: Two space-separated integers, N and M

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.

Output

* Line 1: A single integer that is the number of cows who are considered popular by every other cow.

Sample Input

Sample Output

Hint

Cow 3 is the only cow of high popularity.

在同一个强连通分量中的点互相可以到达（互相崇拜），问题转化为将每个强连通分量压缩为点后新的图是否是DAG并且所有的点都可以到达最后一个点（SCC缩后）。

自己开始的思路是，用Kosaraju算法求好所有的scc后，拓扑序也已求好，在拓扑序中最后访问到的一个scc就是可能的答案，再以反向边从该点dfs，如果图中所有的点都能到达该点，那么该点所在的scc的结点数就是答案，否则不合法。

看题解，其思路更直观，缩点后新图判断出度为0的点个数，若为0，则整个图处于大scc中，若为1，则该点代表的scc结点数就是答案，若大于1，则不合法。因为只需要知道点的出度是不是0，不需要知道具体是多少，所以不需要新图建新边，直接遍历原边，若两点不在同一scc，就累加来源点的出度，同一scc每个点都算出度累加，就行了，不会影响结果正确性。

Kosaraju：

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define maxn 10000+1000

int n,m;
vector<int> G[maxn],G2[maxn];
vector<int> S;
int vis[maxn],sccno[maxn],scc_cnt;
int ans;

void AddEdge(int x,int y)
{
	G[x].push_back(y);
	G2[y].push_back(x);
}
void dfs1(int u)
{
	if(vis[u])return ;
	vis[u]=1;
	for(int i=0;i<G[u].size();i++)dfs1(G[u][i]);
	S.push_back(u);
}
void dfs2(int u)
{
	if(sccno[u])return ;
	sccno[u]=scc_cnt;
	for(int i=0;i<G2[u].size();i++)dfs2(G2[u][i]);
}
void dfs(int u)
{
	if(vis[u])return ;
	vis[u]=1;
	for(int i=0;i<G2[u].size();i++)dfs(G2[u][i]);
}
void find_scc()
{
	for(int i=1;i<=n;i++)dfs1(i);
	for(int i=n-1;i>=0;i--)if(!sccno[S[i]])
	{
		scc_cnt++;
		dfs2(S[i]);
	}
}
int check()
{
	int last;
	memset(vis,0,sizeof(vis));
	for(int i=n-1;i>=0;i--)if(!vis[sccno[S[i]]])last=S[i],vis[sccno[S[i]]]=1;
	bool ok=1;
	memset(vis,0,sizeof(vis));
	dfs(last);
	for(int i=1;i<=n;i++)if(!vis[i])ok=0;
	if(ok)for(int i=1;i<=n;i++)if(sccno[i]==sccno[last])ans++;
	return ans;
}

int main()
{
//	freopen("input.in","r",stdin);
	int x,y;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		AddEdge(x,y);
	}
	find_scc();
	printf("%d\n",check());
	return 0;
}

Tarjan：

#include<cstdio>
#include<vector>
#include<cstring>
#include<stack>
using namespace std;
#define maxn 10000+1000

int n,m;
vector<int> G[maxn];
stack<int> S;
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

void dfs(int u)
{
	pre[u]=lowlink[u]=++dfs_clock;
	S.push(u);
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(!pre[v])
		{
			dfs(v);
			lowlink[u]=min(lowlink[u],lowlink[v]);
		}
		else if(!sccno[v])
		{
			lowlink[u]=min(lowlink[u],pre[v]);
		}
	}
	if(lowlink[u]==pre[u])
	{
		scc_cnt++;
		for(;;)
		{
			int x=S.top();S.pop();
			sccno[x]=scc_cnt;
			if(x==u)break;
		}
	}
}
void find_scc()
{
	for(int i=1;i<=n;i++)if(!pre[i])dfs(i);
}
int check()
{
	int out[maxn]={0};
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<G[i].size();j++)
		{
			if(sccno[i]!=sccno[G[i][j]])out[sccno[i]]++;
		}
	}
	int cnt=0;
	for(int i=1;i<=scc_cnt;i++)if(out[i]==0)cnt++;
	if(cnt>1)return 0;
	else if(cnt==0)return n;
	else for(int i=1;i<=scc_cnt;i++)if(out[i]==0)
	{
		int ans=0;
		for(int j=1;j<=n;j++)if(sccno[j]==i)ans++;
		return ans;
	}
}

int main()
{
//	freopen("input.in","r",stdin);
	int x,y;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
	}
	find_scc();
	printf("%d\n",check());
	return 0;
}