POJ 1236 Network of Schools （连通图 - Garbow 算法）

POJ 1236 Network of Schools

? 校园网：给定N所学校和网络，目标是分发软件其他学校都可收到，求①所需最少分发学校数；②若任选学校都能收到，最低新增边数。

思路：同一个强连通分量内的顶点合并为一个，在这个DAG上计算出度和入度。①其实是求入度为0的顶点数，②则是求0出度和0入度顶点数的较大者，因为要将这两类顶点连起来。

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cstdio>

using namespace std;
#define MAX_V 100 + 10
#define ms(a,b) memset(a,b,sizeof a)

int V;                      // 顶点数
vector<int> G[MAX_V];       // 图的邻接表表示
vector<int> rG[MAX_V];      // 反向图
vector<int> vs;             // 后序遍历顺序的顶点列表
bool book[MAX_V];           // 访问标记
int cmp[MAX_V];             // 所属强连通分量的拓补序
int in[MAX_V], out[MAX_V];  // 入度、出度

void add_Edge(int from, int to) {
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(const int &v) {
	book[v] = true;
	for (int i = 0; i < G[v].size(); ++i) {
		if (!book[G[v][i]])
			dfs(G[v][i]);
	}
	vs.push_back(v);
}

void rdfs(const int& v, const int& k) {
	book[v] = true;
	cmp[v] = k;
	for (int i = 0; i < rG[v].size(); ++i) {
		if (!book[rG[v][i]])
			rdfs(rG[v][i], k);
	}
}

int scc() {
	ms(book, false); vs.clear();
	for (int v = 0; v < V; ++v) {
		if (!book[v])
			dfs(v);
	}
	ms(book, false);
	int k = 0;
	for (int i = vs.size() - 1; i >= 0; --i) {
		if (!book[vs[i]])
			rdfs(vs[i], k++);
	}
	return k;
}

int main() {
	//freopen("in.txt","r",stdin);
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//尝试过快读，莫名比scanf和关闭流同步还速度慢
	cin >> V;
	for (int u = 0, v; u < V; ++u) {
		while (cin>>v  && v)
			add_Edge(u, --v);
	}

	int n = scc();
	// 特殊情况
	if (n == 1)return cout << 1 << endl << 0, 0;

	for (int u = 0; u < V; ++u)
		for (int i = 0; i < G[u].size(); ++i) {
			int v = G[u][i];
			if (cmp[u] != cmp[v])	// 强连通分量算一个点
				++out[cmp[u]], ++in[cmp[v]];
		}

	int zero_in = 0, zero_out = 0;
	for (int i = 0; i < n; ++i){
		if (in[i] == 0) ++zero_in;
		if (out[i] == 0)++zero_out;
	}
	cout << zero_in << endl << max(zero_in, zero_out) << endl;
}