POJ|POJ 1236 【强连通图+缩点】.cpp POJ1236【强连通图+缩点】.cpp

题意：
给出n个学校的兄弟学校..<单方面认为>
如果给了一个软件给某个学校..他就会把这个软件给他的兄弟学校..
然后求两个解:
1st: 至少准备多少个软件..可以使所有的学校都有这个软件..
2nd:至少加多少条边..可以使只给一个软件..就能让所有学校都得到这个软件..
输入:
一个n 代表有n个学校..
接下来n行..
【POJ|POJ 1236 【强连通图+缩点】.cpp】第i行给出第i个学校的兄弟学校(单方面认为)的列表..以0结束..

输出两个解的结果..

思路：
缩点之后把原图变成一个有向无环图..

两个解可以看成是：
1st：把该有向无环图看成一个森林..求的就是有多少棵树..<即入度为0的根节点的个数>
2nd：求加多少条边可以使森林变成强连通图..
自己画图可以看出..找出入度为0和出度为0中最大的个数..即为要连的边..
因为如果入度为0比出度为0少..则从入度为0的点往出度为0的点连边..
可以使之变成一个强连通分量..

Tips：
※：求入度和出度的时候..可以直接遍历缩点后的图然后求..
※：注意求第二个解的时候..如果缩点后的图已经是强连通分量..则不用加边..
但是理论上求出来的入度为0和出度为0的个数都会是 1
所以要特别判断一下..
Code:

文章图片

文章图片
View Code

1 #include 2 #include 3 #include 4 using namespace std; 5 const int INF = 0x1f1f1f1f; 6 #define clr(x) memset(x, 0, sizeof(x)) 7 const int MAXN = 110; 8 9 struct Edge 10 { 11int to; 12int next; 13 }edge[10000010]; 14 int head[MAXN]; 15 int tot; 16 17 void add(int s, int u) 18 { 19edge[tot].to = u; 20edge[tot].next = head[s]; 21head[s] = tot++; 22 } 23 24 int dfn[MAXN], low[MAXN]; 25 int ins[MAXN], sta[MAXN], col[MAXN]; 26 int ti, top, cnt; 27 int n; 28 29 void tarjan(int u) 30 { 31int i, k; 32dfn[u] = low[u] = ++ti; 33ins[u] = 1; 34sta[++top] = u; 35for(i = head[u]; i != -1; i = edge[i].next) { 36k = edge[i].to; 37if(dfn[k] == 0) { 38tarjan(k); 39low[u] = min(low[u], low[k]); 40} else if(ins[k]) { 41low[u] = min(low[u], dfn[k]); 42} 43} 44if(dfn[u] == low[u]) { 45cnt++; 46do 47{ 48k = sta[top--]; 49col[k] = cnt; 50ins[k] = 0; 51}while(u != k); 52} 53 54 } 55 56 void solve_ta() 57 { 58int i, k; 59ti = top = cnt = 0; 60clr(dfn); 61for(i = 1; i <= n; ++i) 62if(!dfn[i]) 63tarjan(i); 64 } 65 66 int ansa, ansb; 67 int in[MAXN], out[MAXN]; 68 void solve() 69 { 70int i, j, k; 71ansa = ansb = 0; 72clr(in), clr(out); 73solve_ta(); 74 75for(i = 1; i <= n; ++i) { 76for(j = head[i]; j != -1; j = edge[j].next) { 77k = edge[j].to; 78if(col[i] != col[k]) { 79in[col[k]]++; 80out[col[i]]++; 81} 82} 83} 84 85int tmpa = 0, tmpb = 0; 86for(i = 1; i <= cnt; ++i) { 87if(in[i] == 0) tmpa++; 88if(out[i] == 0) tmpb++; 89} 90 91ansa = tmpa; 92ansb = max(tmpa, tmpb); 93if(cnt == 1) ansb = 0; 94 } 95 96 int main() 97 { 98int i, j, k; 99int a, b, w; 100while(scanf("%d", &n) != EOF) 101{ 102tot = 0; 103memset(head, 0xff, sizeof(head)); 104 105for(i = 1; i <= n; ++i) { 106while(scanf("%d", &a), a) { 107add(i, a); 108} 109} 110 111solve(); 112printf("%d\n%d\n", ansa, ansb); 113} 114return 0; 115 }

题目链接：http://poj.org/problem?id=1236
转载于:https://www.cnblogs.com/Griselda/archive/2012/10/04/2711761.html