#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#define GSIZE 10010
#define ESIZE 50010

int order[GSIZE],e,visit[GSIZE],flag[GSIZE],out[ESIZE],in[ESIZE],degree[GSIZE];
struct Point
{
	int id;
	struct Point *next;
}mapa[GSIZE],mapt[GSIZE];
void insert(int a, int b)
{
	Point *p = &mapa[a];
	while(p->next )
		p = p->next;
	p->next = (struct Point *)malloc(sizeof(struct Point));
	p = p->next;
	p->id = b;
	p->next = NULL;
	p = &mapt[b];
	while(p->next )
		p = p->next;
	p->next = (struct Point *)malloc(sizeof(struct Point));
	p = p->next;
	p->id = a;
	p->next = NULL;
}
void dfsa(Point *k)
{	
	visit[k->id] = true;
	Point *p = k->next;
	while(p){
		if(!visit[p->id]){
			p = &mapa[p->id];
			dfsa(p);
		}
		p = p->next;
	}
	order[e++] = k->id;
}
void dfst(Point *k)
{
	visit[k->id] = true;
	Point *p = k->next;
	flag[k->id] = e;
	while(p != NULL){
		if(!visit[p->id]){
			p = &mapt[p->id];
			dfst(p);
		}
		p = p->next;
	}
}
int main()
{
	int n,m,i,x,y;
	scanf("%d%d",&n,&m);
	for(i = 1; i <= n; i++){
		mapa[i].next = NULL;
		mapa[i].id = i;
		mapt[i].next = NULL;
		mapt[i].id = i;
	}
	for(i = 0; i < m; i++){
		scanf("%d %d",&x,&y);
		insert(x,y);
		out[i] = x;
		in[i] = y;
	}
	Point *temp;
	memset(visit,0,sizeof(visit));
	e = 0;
	for(i = 1; i <= n; i++){
		if(!visit[i]){
			temp = &mapa[i];
			dfsa(temp);
		}
	}
	e = 0;
	memset(flag,0,sizeof(flag));
	memset(visit,0,sizeof(visit));
	for(i = n-1; i >= 0; i--){
		if(!visit[order[i]]){
			temp = &mapt[order[i]];
			dfst(temp);
			e++;
		}
	}
	memset(degree,0,sizeof(degree));
	for(i = 0; i < m; i++){
		int eee = flag[out[i]];
		int sss = flag[in[i]];
		if(eee != sss)
			degree[eee]++;
	}
	int pos,tflag = 0;
	for(i = 0; i < e; i++){
		if(degree[i] == 0){
			pos = i;
			tflag++;
		}
	}
	if(tflag != 1)
		printf("0\n");
	else{
		int out = 0;
		for(i = 1; i <= n; i++)
			if(flag[i] == pos)
				out++;
			printf("%d\n",out);
	}
	return 0;
}

• ft~~~好低级的错误，大家当我没问。 (2253) madongtest 2006-09-10 09:51:02