2369706_tle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INIT (Edge *)malloc(sizeof(Edge))

int n, m;
typedef struct node
{
	int adj;
	struct node *next;
}Edge;

struct Node
{
	Edge *head;
}pot[10001];
int visited[10001];
int ans[10001];

void dfs(int v)
{
	Edge *s;

	s = pot[v].head;
	visited[v] = 1;
	ans[v]++;
	while(s->next)
	{
		if(!visited[s->next->adj])
			dfs(s->next->adj);
		s = s->next;
	}
}

int main()
{
	int i;
	Edge *s;
	int a, b;

	scanf("%d%d",&n,&m);
	for(i = 0; i < n; i++)
	{
		pot[i].head = INIT;
		pot[i].head->next = NULL;
	}
	for(i = 0; i < m; i++)
	{
		scanf("%d%d",&a,&b);
		a--,b--;
		s = INIT;
		s->adj = b;
		s->next = pot[a].head->next;
		pot[a].head->next = s;
	}
	memset(ans,0,sizeof(ans));
	for(i = 0; i < n; i++)
	{
		memset(visited,0,sizeof(visited));
		dfs(i);
	}
	int res = 0;
	for(i = 0; i < n; i++)
		if(ans[i]==n)
			res++;
	printf("%d\n",res);
	return 1;
}