> #define MAXV 1001
> #define MAXM 6000
> #include<cstdlib>
> #include<cstdio>
> struct Node
> {
> 	int no; 
> 	Node* next;
> };
> 
> int nodesize;
> Node buffer[MAXM*2];
> int bufPos;
> 
> Node*Adj[MAXV][2];
> 
> int id[MAXV], postR[MAXV], postI[MAXV];
> int cnt, scnt;
> 
> bool ker[MAXV][MAXV];
> /**
> * Insert a edge into the graph,  and it's reverse respertively.
> **/
> int insert(int i, int j)
> {
> 	Node*t=buffer+nodesize*bufPos++;
> 	(*t).no=j;
> 	(*t).next=Adj[i][0];
> 	Adj[i][0]=t;
> 	
> 	t=buffer+nodesize*bufPos++;
> 	(*t).no=i;
> 	(*t).next=Adj[j][1];
> 	Adj[j][1]=t;
> }
> 
> void dfsR(Node* r, int w, int n)
> {
> 	id[w]=scnt;
> 	for (Node* t=r; t!=NULL; t=(*t).next)
> 	{
> 		int v=(*t).no;
> 		if (id[v]==-1)
> 			dfsR(Adj[v][n], v, n);
> 	}
> 	postI[cnt++]=w;
> }
> 
> /***
> **Find the strong connected components of the graph
> ***/
> void sc(int n)
> {
> 	int v;
> 	cnt=1; scnt=1;
> 	for (v=1; v<=n; v++) id[v]=-1;
> 
> 	for (v=1; v<=n; v++)
> 	{
> 		if (id[v]==-1)
> 		{
> 			dfsR(Adj[v][1], v, 1);
> 		}
> 	}
> 	for (v=1; v<=n; v++)
> 	{
> 		postR[v]=postI[v];		
> 	}
> 
> 	cnt=1; scnt=1;
> 	for (v=1; v<=n; v++) id[v]=-1;
> 	for (v=n; v>0; v--)
> 	{
> 		if (id[postR[v]]==-1)
> 		{
> 			dfsR(Adj[postR[v]][0], postR[v], 0);
> 		}
> 		scnt++;
> 	}
> 
> }
> 
> bool runRch()
> {
> 	int n, m;
> 	int i, j, k;
> 	int a, b;
> 	scanf("%d%d", &n, &m);
> 	for (i=1; i<=n; i++)
> 		Adj[i][0]=Adj[i][1]=NULL;
> 	for (i=0; i<m; i++)
> 	{
> 		scanf("%d%d", &a, &b);
> 		insert(a, b);
> 	}	
> 	sc(n);
> 	for (i=1; i<=n; i++)
> 		for (j=1; j<=n; j++)
> 			ker[i][j]=false;
> 
> 	for (i=1; i<=n; i++)
> 		for (Node*p=Adj[i][0]; p!=NULL; p=(*p).next)
> 		{
> 			int w=(*p).no;
> 			ker[id[i]][id[w]]=true;
> 		}
> 
> 	for (k=1; k<scnt; k++)
> 		for (i=1; i<scnt; i++)
> 			if (ker[i][k])
> 			for (j=1; j<scnt; j++)
> 				if (ker[k][j])
> 					ker[i][j]=true;
> 	/**for (i=1; i<=n; i++)
> 	{
> 		printf("%d", id[i]);
> 	}
> 	printf("\n");**/
> 	int ii, ij;
> 	for (i=1; i<=n; i++)
> 		for (j=1; j<=n; j++)
> 		{	ii=id[i]; ij=id[j];
> 			if (ii!=ij)
> 				if (!ker[ii][ij]&&!ker[ij][ii])
> 					return false;
> 		}
> 
> 	return true;
> }
> 
> 
> int main()
> {
> 	int t;
> 	nodesize=sizeof(Node);
> 	scanf("%d", &t);
> 	for (; t>0; t--)
> 	{
> 		bufPos=0;
> 		if (runRch())
> 		{
> 			printf("Yes\n");
> 		}
> 		else
> 		{
> 			printf("No\n");
> 		}
> 	}
> }

• 数组换大点试试 (0) hit_hith 2014-08-13 15:11:04