POJ 2186 Popular Cows (tarjan缩点 染色 出度标记)

虽然不是很难，但是每次都能写着写着有点迷，还是记录一下吧

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 1e5+10,maxm = 5e5+10;
int n,m,timing,tot,cnt;
int color[maxn],head[maxn],sum[maxn],dfn[maxn],low[maxn],vis[maxn],du[maxn];
struct Edge{ int to,nxt;}e[maxm];
int stack[maxn],top;
void add(int from,int to)
{
	e[tot].to = to, e[tot].nxt = head[from];
	head[from] = tot++;
}
void tarjan(int fa)
{
	dfn[fa] = low[fa] = ++timing;
	stack[++top] = fa; vis[fa] = 1;
	for(int i = head[fa]; ~i; i = e[i].nxt)
	{
		int to = e[i].to;
		if(!dfn[to])
		{
			tarjan(to);
			low[fa] = min(low[fa],low[to]);
		}
		else if(vis[to]) low[fa] = min(low[fa],dfn[to]); //wdnmd
	}
	if(dfn[fa]==low[fa])
	{
		int len = top;
		cnt++;
		while(stack[top] != fa) color[stack[top--]] = cnt;
		color[stack[top--]] = cnt;
		sum[cnt] = len-top;
	}
	
}
int main()
{
	memset(head,-1,sizeof(head)); tot = 0;
	scanf("%d%d",&n,&m);
	for(int i = 0,u,v; i < m; ++i)
	{
		scanf("%d%d",&u,&v);
		add(u,v);  
	}
	for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= n; ++i)
	for(int j = head[i]; ~j; j = e[j].nxt)
	if(color[i] != color[e[j].to]) du[color[i]]++;
	int s = 0,p;
	for(int i = 1; i <= cnt; ++i)
	{
		if(du[i]==0) s++,p=i;
	}
	if(s==1) printf("%d",sum[p]);
	else printf("0");
	
}