2021463_ac_139ms_2616k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 127 行

//Kosaraju's algorithm
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAXV 10001

int N, n;
long M;
int count;
int order[MAXV];
int visited[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;
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;
	long i;

	for(i = 0; i < M; i++)
	{
		scanf("%d%d",&u,&v);
		insert(u-1,v-1);
	}
}

void init()
{
	int i;

	scanf("%d%ld",&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;
	s = GA.adjlist[v].firstedge;
	while(s)
	{
		if(!visited[s->adjvex])
		{
			n++;
			dfs_a(s->adjvex);
		}
		s = s->next;
	}
}

void solve()
{
	int i;

	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]])
		{
			n = 0;
			dfs_a(order[i]);
			if(n)
				count++;
		}
	printf("%d",count);
}

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