pku2186_a.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

/*
	求有向图的强连通分量的Kosaraju's algorithm
	By Sempr ---- 2006.06.15
*/
#include <stdio.h>
#include <string.h>
#define G_size 100000
#define V_size 11000

typedef struct Graph
{
	int id;
	int next;
} Graph;

typedef struct Edge
{
	int s, e;
} Edge;

Edge E[G_size];
Graph GA[G_size], GT[G_size]; //
int N, M;
int G_end;
int order[V_size], id[V_size], vis[V_size], in[V_size];
int cnt, scnt, pos;

void Insert(int s, int e) //建立原图和逆图
{
	int p;
	p = s;
	while (GA[p].next)
		p = GA[p].next;
	GA[G_end].id = e;
	GA[p].next = G_end;

	p = e;
	while (GT[p].next)
		p = GT[p].next;
	GT[G_end].id = s;
	GT[p].next = G_end;
	
	G_end++;
}

void DFST(int x) //对逆图进行搜索
{
	int p, q;
	vis[x] = 1;
	p = GT[x].next;
	while (p)
	{
		q = GT[p].id;
		if (!vis[q])
			DFST(q);
		p = GT[p].next;
	}
	order[cnt++] = x;
}

void DFSA(int x) //对原图进行搜索
{
	int p, q;
	vis[x] = 1;
	id[x] = cnt;
	p = GA[x].next;
	while (p)
	{
		q = GA[p].id;
		if (!vis[q])
			DFSA(q);
		p = GA[p].next;
	}
}

void OutGA() //输出原图
{
	int i, p;
	printf("GA:\n");
	for (i = 0; i < N; i++)
	{
		printf("i = %d:", i);
		p = GA[i].next;
		while (p)
		{
			printf("%d ", GA[p].id);
			p = GA[p].next;
		}
		printf("\n");
	}
}

void OutGT() //输出逆图
{
	int i, p;
	printf("GT:\n");
	for (i = 0; i < N; i++)
	{
		printf("i = %d:", i);
		p = GT[i].next;
		while (p)
		{
			printf("%d ", GT[p].id);
			p = GT[p].next;
		}
		printf("\n");
	}
}

void Solve() //主要函数
{
	int s, e;
	int i;
	
	memset(GA, 0, sizeof(GA));
	memset(GT, 0, sizeof(GT));
	memset(E, 0, sizeof(E));
	G_end = N + 1;
	
	for (i = 0; i < M; i++)
	{
		scanf("%d %d", &s, &e);
		E[i].s = s - 1;
		E[i].e = e - 1;
		Insert(s - 1, e - 1);
	}
	
	memset(vis, 0, sizeof(vis));
	cnt = 0;
	for (i = 0; i < N; i++)
	{
		if (!vis[i])
		{
			DFST(i);
		}
	}

	memset(vis, 0, sizeof(vis));
	cnt = 0;
	for (i = N - 1; i >= 0; i--)
	{
		if (!vis[order[i]])
		{
			DFSA(order[i]);
			cnt++;
		}
	}

	for (i = 0; i < M; i++)
	{
		s = id[E[i].s];
		e = id[E[i].e]; 
		if (s != e)
		{
			in[s]++;
		}
	}
	scnt = cnt;
	cnt = 0;
	for (i = 0; i < scnt; i++)
	{
		if (in[i] == 0)
		{
			pos = i;
			cnt++;
		}
	}
	if (cnt != 1)
	{
		printf("0\n");
	}
	else
	{
		cnt = 0;
		for (i = 0; i < N; i++)
		{
			if (in[id[i]] == pos)
			{
				cnt++;
			}
		}
		printf("%d\n", cnt);
	}
}

int main()
{
	while (EOF != scanf("%d %d", &N, &M))
		Solve();
	return 0;
}