usaco_5_3_3_schlnet-强连通分量.cpp

usaco自己做的1到5章的代码

/*
 ID: wangyuc2
PROG: schlnet
LANG: C++
*/
/*
这是一道收缩强连通分量的题。 

该题描述的是一个有向图。我们都知道，在一个有向图强连通分量中从任意一个顶点开始，可以到达强连通分量的每个顶点。由此可以把该题中所有强连通分量收缩成分别一个顶点，则入度为0的顶点就是最少要接受新软件副本的学校。 

第二问就是，问至少添加多少条边，才能使原图强连通。也就问在收缩后的图至少添加多少条边，才能使之强连通。 

可以知道，当存在一个顶点入度为0或者出度为0的时候，该图一定不是强连通的。为了使添加的边最少，则应该把入度为0顶点和出度为0的顶点每个顶点添加1条边，使图中不存在入度为0顶点和出度为0的顶点。 

当入度为0的顶点多于出度为0的顶点，则应添加的边数应为入度为0的顶点的个数。当出度为0的顶点多于出入度为0的顶点，则应添加的边数应为出度为0的顶点的个数。 

这样就可以解决问题了。但是不要忘了还有特殊的情况，当原图本身就是强连通分量时，收缩成一个顶点，该顶点入度和出度都为0，但第一问应为1，第二问应为0。 

求强连通分量，我用的两遍深搜的Kosaraju算法，时间复杂度为O(n)。把找到的每个强连通分量收缩为一的顶点，组成新图。设r(x)为x所在的强连同分量的代表节点，如果原图中存在边e(x,y)，那么新图中有边e(r(x),r(y)) 。然后根据点的邻接关系统计出度和入度即可。 




[编辑] 求强连通分量的另一种方法 
Sinya觉得写深搜求太麻烦了，所以Sinya就用了另一种求强连通分量的方法。 

用froyed算出两点间是否可以互相到达。然后枚举任意两个顶点Vi还有Vj，如果两个点互相可以到达，那么他们就是属于同一个强连通分量了。 

虽然是O(n^3)的算法。可是这道题能过。可以大幅降低编程复杂度。 

但是Sinya又觉得我们要精益求精，所以大家也要掌握深搜法哦 




[编辑] 旁门左道 
本题我用的是一种非标准算法。不知道为什么对，但是过了。 

第一问是求最小点基。这个我是分步骤计算的： 

首先，所有入度为0的点肯定要得到软件，因为如果得不到，那么没有别的点来通过网络传输给它。找出所有入度为0的点，把这些点以及他所能到达的点全都作上标记。 

对于剩下的点，找出块的个数，这里定义两个点连通当且仅当两个点之间存在路径，不考虑方向。原因很简单，两个点之间只要其中一个能到达另一个即可，这样的块中必然有一个点可以作为起点，而由于前一步已经把入度为0的点去掉了，所以这样的块一定从起点可以到达所有点。 

第一问的答案就是上述两者个数之和。 

第二问首先统计整个图的入度为0和出度为0的点的个数，前者再加上上一步求出来的块的个数（当整个图就是一个块的时候不用加），答案就是两者中的较大者。 

*/
/*
Kosaraju算法
来自"NOCOW"
跳转到: 导航, 搜索
/*这是一个求图的强连通分量的算法。*/ 
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 11000 
 
vector< vector< int > > path;
vector< vector< int > > npath;
int n,m, scc;
int order[NMAX], order_pos, id[NMAX], id_total[NMAX];
bool vis[NMAX];
int out_degre[NMAX];
 
void dfs(int pos)
{
	int i,j,l;
	vis[pos] = true;
	l = path[pos].size();
	for (i=0;i<l;i++) {
		j = path[pos][i];
		if (!vis[j]) {
			dfs(j);
		}
	}
	order[ order_pos ++ ] = pos;//make order
}
 
void ndfs(int pos)
{
	int i,j,l;
	vis[pos] = true;
	id[pos] = scc;
	l = npath[pos].size();
	for (i=0;i<l;i++) {
		j = npath[pos][i];
		if (!vis[j]) {
			ndfs(j);
		}
	}
}
 
void Kosaraju()
{
	int i,j,l;
	//dfs in original graph
	memset(vis, 0, sizeof(vis));
	for (i=1; i<=n ;i++) {
		if (!vis[i]) {
			dfs(i);
		}
	}
	//dfs in inverse graph
	memset(vis, 0, sizeof(vis));
	memset(id, 0, sizeof(id));
	scc = 1;
	for (i=order_pos-1; i>=0 ;i--) {
		if (!vis[ order[i] ]) {
			ndfs(order[i]);
			scc ++;
		}
	}
	//statist
	scc --;
	memset(id_total, 0, sizeof(id_total));
	for (i=1;i<=n;i++) {
		id_total[ id[i] ] ++;
	}
 
	memset(out_degre, 0, sizeof(out_degre));
	for (i=1;i<=n;i++) {
		l = path[i].size();
		int id1 = id[i];
		for (j=0;j<l;j++) {
			int id2 = id[ path[i][j] ];
			if (id1 != id2) {//id1 -> id2
				out_degre[id1] ++;
			}
		}
	}
	int ans_id,zero_degre = 0;
	for (i=1;i<=scc;i++) {
		if (out_degre[i] == 0) {
			zero_degre ++;
			ans_id = i;
		}
	}
 
	if (zero_degre > 1) {
		printf("0\n");
	}
	else {
		printf("%d\n",id_total[ ans_id ]);
	}
}
 
int main()
{
	int i,j;
	while (scanf("%d %d",&n,&m)==2) {
		path.resize(n+10);
		npath.resize(n+10);
		for (i=0;i<=n;i++) {
			path[i].clear();
			npath[i].clear();
		}
		order_pos = 0;
		//set graph
		for (i=0;i<m;i++) {
			int x,y;
			scanf("%d %d",&x,&y);
			path[x].push_back(y);
			npath[y].push_back(x);
		}
		Kosaraju();
	}
}
*/
//written by CmYkRgB123
#include <iostream>
#include <fstream>
#define MAXN 101
#define max(x,y) ((x)>(y)?x:y)

using namespace std;

ifstream fi("schlnet.in");
ofstream fo("schlnet.out");

int N,M;
int adjl[MAXN][MAXN],fdjl[MAXN][MAXN];
bool vis[MAXN],dis[MAXN][MAXN];
int belong[MAXN],ind[MAXN],oud[MAXN],i0,o0;


void init()
{
	int t,i;
	fi >> N;
	for (i=1;i<=N;i++)
	{
		fi >> t;
		while (t)
		{
			adjl[i][ ++adjl[i][0] ]=t;
			fdjl[t][ ++fdjl[t][0] ]=i;
			fi >> t;
		}
	}
}

void dfs(int i)
{
	int j,k;
	vis[i]=true;
	for (k=1;k<=adjl[i][0];k++)
	{
		j=adjl[i][k];
		if (!vis[j])
			dfs(j);
	}
}

void fdfs(int i)
{
	int j,k;
	belong[i]=M;
	for (k=1;k<=fdjl[i][0];k++)
	{
		j=fdjl[i][k];
		if (vis[j] && !belong[j])
			fdfs(j);
	}
}

void solve()
{
	int i,j,k;
	for (i=1;i<=N;i++)
	{
		if (!belong[i])
		{
			dfs(i);
			M++;
			fdfs(i);
			memset(vis,0,sizeof(vis));
		}
	}
	for (i=1;i<=N;i++)
	{
		for (k=1;k<=adjl[i][0];k++)
		{
			j=adjl[i][k];
			dis[belong[i]][belong[j]]=true;
		}
	}
	for (i=1;i<=M;i++)
	{
		for (j=1;j<=M;j++)
		{
			if (i!=j && dis[i][j])
			{
				oud[i]++;
				ind[j]++;
			}
		}
	}
	for (i=1;i<=M;i++)
	{
		if (ind[i]==0)
			i0++;
		if (oud[i]==0)
			o0++;
	}
}

void print()
{
	if (M==1)
		fo << 1 << endl << 0 << endl;
	else
	{
		fo << i0 << endl;
		fo << max(i0,o0) << endl;
	}
	fi.close();
	fo.close();
}

int main()
{
	init();
	solve();
	print();
	return 0;
}