#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");
		}
	}
}

• Re: 贴在这里， 谁看看吧， 非常非常感谢 (2520) hit_hith 2014-08-13 15:10:29
  • 数组换大点试试 (0) hit_hith 2014-08-13 15:11:04