POJ 1236 Network of Schools 强连通图

Description

Input

Output

Sample Input

5
2 4 3 0
4 5 0
0
0
1 0

Sample Output

1
2

图论题目，需要解决问题：
1 使用Tarjan算法求子强连通图

2 标识顶点属于哪个子强连通图

3 计算各个子强连通图的零入度数和零出度数

图论中高级内容了，是有点难度的，不细心一点肯定会出错的。

这次本博主认真注解好几乎每个语句，希望大家可以follow我的程序。

#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N = 101;//最大的顶点数
vector<int> graAdj[MAX_N];//vector表示邻接表法
int visNo[MAX_N];//记录深搜各个顶点的访问顺序标号
int lowLink[MAX_N];//连通图的最低标识号，记录好是否递归到已经访问过的顶点了，如果是，那么就以最低的顶点访问顺序标号为，这样可以统一子连通图的标号。通过判断当前最低连通图的标识号和访问顺序号是否一致来判断是否找到了一个子强连通图
int dfsNo;//记录深搜总的访问号
int connectNo;//当前的子强连通图的标号，最终为所有子强连通图的数量
int markNo[MAX_N];//markNo[v]代表顶点v属于子强连通图markNo[v]，其值就为子强连通图
int in[MAX_N], out[MAX_N];//分别记录一个子强连通图的入度数和出度数
stack<int> stk;//深搜顶点入栈，找到子强连通图时候出栈，直到当前顶点数，所有点都属于同一个子强连通图

//深搜查找子强连通图，并记录好顶点属于哪个子强连通图
void getStrongConnected(int u)
{
	visNo[u] = lowLink[u] = ++dfsNo;//第一次进入当前顶点的时候的初值
	int n = (int)graAdj[u].size();
	stk.push(u);
	for (int i = 0; i < n; i++)//遍历当前顶点的所有连接点
	{
		int v = graAdj[u][i];
		if (!visNo[v])//没有访问过的时候
		{
			getStrongConnected(v);//递归
			lowLink[u] = min(lowLink[u], lowLink[v]);//记录最低序号
		}
		//已经访问过，但是还在栈里面，即还没有记录该顶点属于哪个强连通图
		else if (!markNo[v]) lowLink[u] = min(lowLink[u], lowLink[v]);
	}
	if (visNo[u] == lowLink[u])//当前访问顺序号等于最低标号，
	{//那么就是找到了一个子强连通图
		++connectNo;//每次要增加全局的连通标号
		int v;
		do
		{
			v = stk.top(); stk.pop();
			markNo[v] = connectNo;//顶点对用强连通图号
		} while (u != v);
	}
}

void Tarjan(int n)
{
	//前期清零工作
	dfsNo = 0, connectNo = 0;
	fill(visNo, visNo+n+1, 0);
	fill(lowLink, lowLink+n+1, 0);
	fill(markNo, markNo+n+1, 0);
	while (!stk.empty()) stk.pop();

	for (int u = 1; u <= n; u++)
	{
		//某些顶点也许是分离的，就是图的顶点有不相连的，故此要遍历所有顶点
		if (!visNo[u]) getStrongConnected(u);
	}
}

int main()
{
	int N, u, v;
	scanf("%d", &N);
	for (u = 1; u <= N; u++)
	{
		scanf("%d", &v);
		while (v)//为零表示结束
		{
			graAdj[u].push_back(v);//使用vector建立一个邻接表
			scanf("%d", &v);
		}
	}
	Tarjan(N);//计算子强连通图的个数，并表出各个顶点属于哪个子强连通图
	
	for (u = 1; u <= N; u++)
	{//遍历所有顶点，然后遍历顶点的邻接边，相当于遍历所有边
		for (int i = 0; i < (int)graAdj[u].size(); i++)
		{
			int v = graAdj[u][i];
			if (markNo[u] != markNo[v])//不是属于同一个子强连通图
			{//分别增加该强连通图的入度和出度
				out[markNo[u]]++;
				in[markNo[v]]++;
			}
		}
	}

	int zeroIn = 0, zeroOut = 0;
	for (int i = 1; i <= connectNo; i++)
	{
		if (in[i] == 0) zeroIn++;
		if (out[i] == 0) zeroOut++;
	}
	//入度为零则需要放置一个软件拷贝
	printf("%d\n", zeroIn);
	//变为一个强连通图，分2个情况：1 本身是一个强连通图；2 零入度或出度最大值
	printf("%d\n", connectNo == 1? 0 : max(zeroIn, zeroOut));
	
	return 0;
}