#include<iostream>
#include<cstdio>
using namespace std;
int map[1002][1002],low[1002],dfn[1002],dfdeep,visit[1002];
int Z[1002],head,cur[1002];
int tree[1000][1000],belong[1002];
int n,m,T,num;
void init()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		visit[i]=dfn[i]=low[i]=cur[i]=belong[i]=0;
		for(j=1;j<=n;j++)
			map[i][j]=tree[i][j]=0;
	}
	num=0;
	for(i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		map[x][y]=1;
	}
}
void dfs(int x)
{
	int i;
	head++;
    Z[head]=x;
	cur[x]=1;
	visit[x]=1;
	dfdeep++;
	low[x]=dfn[x]=dfdeep;
	for(i=1;i<=n;i++)
		if(map[x][i])
			if(!visit[i])
			{
				dfs(i);
				if(low[i]<low[x])
					low[x]=low[i];
			}
			else
				if(cur[i])
					if(dfn[i]<low[x])
						low[x]=dfn[i];
	if(low[x]==dfn[x])
	{
		num++;
		while(1)
		{
			if(head<0)
				break;
			int v=Z[head];
			head--;
			belong[v]=num;
			cur[v]=0;
			if(v==x)
				break;
		}
	}
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		init();
		int i,j;
		for(i=1;i<=n;i++)
			if(!dfn[i])
			{
				head=-1;
				dfs(i);
				if(head>=0)
				{
					num++;
					while(1)
					{
						if(head<0)
							break;
			     		int v=Z[head];
				    	head--;
				    	belong[v]=num;
					}
				}
			}
		int length=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(map[i][j]&&belong[i]!=belong[j])
					tree[belong[i]][belong[j]]=1;
		int k;
		for(k=1;k<=num;k++)
			for(i=1;i<=num;i++)
				if(tree[i][k])
					for(j=1;j<=num;j++)
						if(tree[k][j])
							tree[i][j]=true;
		int flag=1;
		for(i=1;i<=num;i++)
			for(j=1;j<=num;j++)
				if(!tree[i][j]&&!tree[j][i]&&i!=j)
					flag=0;
		if(flag)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

• Re:我的更暴力，看看我的强连通分量+传递闭包 (2018) ccc000111 2017-03-23 09:12:33