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

标签：vector   遍历   block   iostream   algorithm   速度   syn   clu   fine   

POJ 1236 Network of Schools

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

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

#include
#include
#include
#include
#include

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

int V;                      // 顶点数
vector G[MAX_V];       // 图的邻接表表示
vector rG[MAX_V];      // 反向图
vector 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 = 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  && v)
			add_Edge(u, --v);
	}

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

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

标签：vector   遍历   block   iostream   algorithm   速度   syn   clu   fine   

原文地址：https://www.cnblogs.com/RioTian/p/13391522.html