POJ 1236 Network of Schools(强连通 + 想法)- from lanshui_Yang
Description
A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school BInput
The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.Output
Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.Sample Input
52 4 3 04 5 0001 0
Sample Output
12
题目大意:有n个学校,学校之间可以传递信息,例如学校 a 可以 传达信息给 b , 即a ——> b , 但 b 不一定 能传递信息给 a 。 告诉你每个学校能够向哪些学校传递信息,然后有两个问题:
问题一:至少要向几个学校传递 原始 信息,才能保证所有学校都能收到信息。
问题二:至少要添加多少组关系(每组关系类型如右:a 可以 向 b 传递信息),才能保证 给任意一个学校原始信息后,其他所有学校都能收到信息。
解题思路:这道题其实就是一个有n个顶点的有向图,先用 tarjan 缩点 , 然后分别统计出 入度为0 和 出度为0 的强连通分量个数ansA 和 ansB,那么, 问题一的答案就是ansA , 问题二的答案就是max(ansA , ansB),但是有特例:当只有一个强连通分量时,问题二的答案就是0 。
下面用两张图来说明一下问题二的连边方式:
请看代码:
#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<vector>#define mem(a , b) memset(a , b , sizeof(a))using namespace std ;const int MAXN = 105 ;vector<int> G[MAXN] ;int id[MAXN] ; // 记录缩点后每个顶点所属的强连通分量int tmpdfn ;int low[MAXN] ;int dfn[MAXN] ;int stap[MAXN] ; // 模拟栈bool vis[MAXN] ;int ind[MAXN] ; // 统计每个强连通分量的入度int od[MAXN] ; // 统计每个强连通分量的出度int top ;int component ; // 统计强连通分量数量int n ;int ansA ;int ansB ;const int INF = 0x7fffffff ;void chu(){ int i ; for(i = 0 ; i <= n ; i ++) G[i].clear() ; mem(id , -1) ; mem(dfn , 0) ; mem(low , 0) ; mem(vis , 0) ; mem(od , 0) ; mem(ind , 0) ; component = 0 ; tmpdfn = 0 ; top = - 1 ;}void init(){ chu() ; int i ; for(i = 1 ; i <= n ; i ++) // 建图 { int b ; for(;;) { scanf("%d" , &b) ; if(b == 0) break ; G[i].push_back(b) ; } }}void tarjan(int u){ vis[u] = true ; stap[++ top] = u ; dfn[u] = low[u] = ++ tmpdfn ; int i ; for(i = 0 ; i < G[u].size() ; i ++) { int v = G[u][i] ; if(!vis[v]) { tarjan(v) ; low[u] = min(low[u] , low[v]) ; } else { low[u] = min(dfn[v] , low[u]) ; } } if(low[u] == dfn[u]) // 缩点 { ++ component ; int tmp ; do { tmp = stap[top --] ; dfn[tmp] = INF ; // 勿忘此处!!,这里是排除其他连通快的影响 !! id[tmp] = component ; } while(tmp != u) ; }}void solve(){ ansA = ansB = 0 ; bool flag = false ; int i ; for(i = 1 ; i <= n ; i ++) { if(!vis[i]) // 注意此处,可能不止一个连通块 { tarjan(i) ; } } int j ; for(i = 1 ; i <= n ; i ++) { for(j = 0 ; j < G[i].size() ; j ++) { int ta , tb ; ta = id[i] ; tb = id[ G[i][j] ] ; if(ta != tb) { ind[tb] ++ ; od[ta] ++ ; } } } for(i = 1 ; i <= component ; i ++) { if(ind[i] == 0) ansA ++ ; if(od[i] == 0) ansB ++ ; } if(component == 1) { ansB = 0 ; } else { ansB = max(ansB , ansA) ; } printf("%d\n%d\n" , ansA , ansB) ;}int main(){ while (scanf("%d" , &n) != EOF) { init() ; solve() ; } return 0 ;}