POJ 1236 Network of Schools(强连通分量)
POJ 1236 Network of Schools
任务A:计算为使得每个学校都能通过网络收到软件,你至少需要准备多少份软件拷贝。
任务B:考虑一个更长远的任务,想确保给任意一个学校发放一个新的软件拷贝,该软件拷贝能发布到网络中的每个学校。为了达到这个目标,必须在列表中增加新成员。计算需要添加新成员的最小数目。
2. 统计出度为0: outcnt 和入度为0: incnt
3. 如果已经为一个强连通分量,答案为0,否则答案为max(incnt, outcnt)
/* ID: [email protected] PROG: LANG: C++ */ #include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> using namespace std; #define INF (1<<30) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, a, n) for (int i = a; i < n; i++) #define per(i, a, n) for (int i = n - 1; i >= a; i--) #define eps 1e-6 #define debug puts("===============") #define pb push_back #define mkp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) #define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m) typedef long long ll; typedef unsigned long long ULL; const int maxn = 110; vector<int> g[maxn]; int n, m, dfn[maxn], low[maxn], scc_cnt, dfs_clock, sccno[maxn]; stack<int> s; void dfs(int u) { low[u] = dfn[u] = ++dfs_clock; s.push(u); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!dfn[v]) { dfs(v); low[u] = min(low[v], low[u]); } else if (!sccno[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { scc_cnt++; while(1) { int x = s.top(); s.pop(); sccno[x] = scc_cnt; if (x == u) break; } } } void find_scc(int n) { mem(dfn, 0); mem(sccno, 0); scc_cnt = dfs_clock = 0; for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i); } int in[maxn], out[maxn]; int incnt, outcnt; int work() { for (int u = 1; u <= n; u++) { for (int i = 0; i < g[u].size(); i++) { int U = sccno[u], V = sccno[g[u][i]]; if (U != V) out[U]++, in[V]++; } } incnt = outcnt = 0; //cout<<scc_cnt<<endl; for (int i = 1; i <= scc_cnt; i++) { if (!in[i]) incnt++; if (!out[i]) outcnt++; } printf("%d\n", incnt); if (scc_cnt == 1) printf("0\n"); else printf("%d\n", max(incnt, outcnt)); } int main () { scanf("%d", &n); for (int i = 1; i <= n; i++) { int x; while(scanf("%d", &x), x) { g[i].pb(x); } } find_scc(n); work(); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。