2329478_wa.cpp

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

#include <algorithm>
#define INIT (edge *)malloc(sizeof(edge))
using namespace std;

int k, n, m;
int pos[1001];
int map[1001];
typedef struct node
{
	int adj;
	struct node *next;
}edge;

struct Node
{
	edge *head;
}adj[10001];

void bfs(int i,int v)
{
	int r, f;
	edge *s;
	int visited[100001];
	int queue[100001];

	memset(visited,0,sizeof(visited));
	f = r = -1;
	queue[++f] = v;
	visited[v] = 1;
	while(f!=r)
	{
		++r;
		s = adj[queue[r]].head;
		while(s->next)
		{
			if(!visited[s->next->adj])
			{
				queue[++f] = s->next->adj;
				visited[s->next->adj] = 1;
				map[s->next->adj] = 1;
			}
			s = s->next;
		}
	}
}

int main()
{
	int i;
	int st, ed;
	edge *s;

	scanf("%d%d%d",&k,&n,&m);
	memset(map,0,sizeof(map));
	for(i = 0; i < k; i++)
	{
		scanf("%d",&pos[i]);
		map[pos[i]-1] = 1;
	}
	for(i = 0; i < n; i++)
	{
		adj[i].head = INIT;
		adj[i].head->next = NULL;
	}
	for(i = 0; i < m; i++)
	{
		scanf("%d%d",&st,&ed);
		st--,ed--;
		s = INIT;
		s->adj = ed;
		s->next = adj[st].head->next;
		adj[st].head->next = s;
	}
	for(i = 0; i < k; i++)
		bfs(i,pos[i]-1);
	int ans = 0;
	for(i = 0; i < n; i++)
		if(map[i]==k)
			ans++;
	printf("%d\n",ans);
	return 1;
}