POJ 1236 Network of Schools(强连通 Tarjan+缩点)

POJ 1236 Network of Schools(强连通 Tarjan+缩点)

ACM

题目地址:POJ 1236

题意: 
给定一张有向图,问最少选择几个点能遍历全图,以及最少添加几条边使得有向图成为一个强连通图。

分析: 
HDU 2767 Proving Equivalences题解)一样的题目,不过多了个问题,其实转化成DAG后就不难考虑了,其实只要选择入度为0的点就行了。

代码

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  File:        1236.cpp
*  Create Date: 2014-07-30 15:13:12
*  Descripton:  Tarjan 
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#include <vector>
#include <stack>
#define repf(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;

const int N = 105;

vector<int> G[N];
stack<int> S;
int low[N], dfn[N], sccno[N], tclock, scccnt;
int id[N], od[N];
int n, rd;

void tarjan(int u) {
	low[u] = dfn[u] = ++tclock;
	S.push(u);

	int sz = G[u].size();
	repf (i, 0, sz - 1) {
		int v = G[u][i];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (!sccno[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}

	if (low[u] == dfn[u]) {
		scccnt++;
		int v = -1;
		while (v != u) {
			v = S.top();
			S.pop();
			sccno[v] = scccnt;
		}
	}
}

void read() {
	repf (i, 1, n) {
		G[i].clear();
		while (scanf("%d", &rd) && rd) {
			G[i].push_back(rd);
		}
	}
}

void find_scc() {
	tclock = scccnt = 0;
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	memset(sccno, 0, sizeof(sccno));

	repf (i, 1, n) {
		if (!dfn[i]) {
			tarjan(i);
		}
	}
}

void solve() {
	if (scccnt == 1) {
		printf("1\n0\n");
		return;
	}

	memset(id, 0, sizeof(id));
	memset(od, 0, sizeof(od));

	repf (u, 1, n) {
		int sz = G[u].size();
		repf (i, 0, sz - 1) {
			int v = G[u][i];
			if (sccno[u] != sccno[v]) {
				id[sccno[v]]++;
				od[sccno[u]]++;
			}
		}
	}

	int idnum = 0, odnum = 0;
	repf (i, 1, scccnt) {
		idnum += (id[i] == 0);
		odnum += (od[i] == 0);
	}

	printf("%d\n%d\n", idnum, max(idnum, odnum));
}

int main() {
	while (~scanf("%d", &n)) {
		read();
		find_scc();
		solve();
	}
	return 0;
}


POJ 1236 Network of Schools(强连通 Tarjan+缩点),古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。