2746472_ac_76ms_2616k.c

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

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAXV 10001

int N;
int M;
int count;
int order[MAXV], id[MAXV];
int visited[MAXV], in[MAXV];
typedef struct node
{
	int adjvex;
	struct node *next;
}EdgeNode;
typedef struct vnode
{
	EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MAXV];
typedef struct ALGraph
{
	AdjList adjlist;
}Graphic;

Graphic GA, GB;
struct NODE
{
	int st,ed;
}Edge[50001];

void insert(int u, int v)
{
	EdgeNode *s;

	s = (EdgeNode *)malloc(sizeof(EdgeNode));
	s->adjvex = v;
	s->next = GA.adjlist[u].firstedge;
	GA.adjlist[u].firstedge = s;
	s = (EdgeNode *)malloc(sizeof(EdgeNode));
	s->adjvex = u;
	s->next = GB.adjlist[v].firstedge;
	GB.adjlist[v].firstedge = s;
}

void input()
{
	int u, v, i;

	memset(in,0,sizeof(in));
	for(i = 0; i < M; i++)
	{
		scanf("%d%d",&u,&v);
		Edge[i].st = u-1,Edge[i].ed = v-1;
		insert(u-1,v-1);
	}
}

void init()
{
	int i;

	scanf("%d%d",&N,&M);
	for(i = 0; i < N; i++)
	{
		GA.adjlist[i].firstedge = NULL;
		GB.adjlist[i].firstedge = NULL;
	}
}

void dfs_b(int v)
{
	EdgeNode *s;

	visited[v] = 1;
	s = GB.adjlist[v].firstedge;
	while(s)
	{
		if(!visited[s->adjvex])
			dfs_b(s->adjvex);
		s = s->next;
	}
	order[count++] = v;
}

void dfs_a(int v)
{
	EdgeNode *s;

	visited[v] = 1;
	id[v] = count;
	s = GA.adjlist[v].firstedge;
	while(s)
	{
		if(!visited[s->adjvex])
		{
			dfs_a(s->adjvex);
		}
		s = s->next;
	}
}

void solve()
{
	int i, t, pos;

	count = 0;
	memset(visited,0,sizeof(visited));
	for(i = 0; i < N; i++)
		if(!visited[i])
			dfs_b(i);
	count = 0;
	memset(visited,0,sizeof(visited));
	for(i = N-1; i >= 0; i--)
		if(!visited[order[i]])
		{
			dfs_a(order[i]);
			count++;
		}
	for(i = 0; i < M; i++)
	{
		if(id[Edge[i].st]!=id[Edge[i].ed])
			in[id[Edge[i].st]]++;
	}
	t = count;
	count = 0;
	for(i = 0; i < t; i++)
	{
		if(in[i]==0)
		{
			pos = i;
			count++;
		}
	}
	if(count==1)
	{
		count = 0;
        for (i = 0; i < N; i++)
        {
            if (in[id[i]] == pos)
                count++;
        }
        printf("%d\n", count);
	}
	else
		printf("0\n");
}

int main()
{
	init();
	input();
	solve();
	return 1;
}