题目链接：http://poj.org/problem?id=1236
题意：给定一个表示n所学校网络连通关系的有向图。现要通过网络分发软件，规则是：若顶点u,v存在通路，发给u，则v可以通过网络从u接收到。
现要求解两个问题：
TaskA: 最少分发给几个学校，就可以使所有的学校都能得到软件。
TaskB: 最少增加几条边，就可以使得，发软件给任一学校，所有学校都可以收到。
思路：先进行强联通分量分解，然后缩点，并计算缩点后每个点的出度、入度。入度为0的点的总数为 a ，出度为0的点总数为 b。a即TaskA的答案，而TaskB的答案为max(a, b)。
求SCC部分参考了 http://blog.csdn.net/dgq8211/article/details/7834292
缩点的做法很暴力，将每个强联通分量重新编号为一个集合，在求SCC时记录belong。
1 #include <cstdio> 2 #include <vector> 3 #include <stack> 4 #include <cstring> 5 using namespace std; 6 const int MAX_N = 105; 7 8 int n; 9 vector<int> G[MAX_N]; 10 stack<int> S; 11 int clock; 12 int scc; 13 int dfn[MAX_N], low[MAX_N]; 14 int inStack[MAX_N]; 15 int belong[MAX_N]; 16 int indeg[MAX_N];//scc的 17 int outdeg[MAX_N]; 18 19 void init(){ 20 scc = 0; 21 clock = 0; 22 memset(dfn, 0, sizeof(dfn)); 23 memset(low, 0, sizeof(low)); 24 memset(inStack, 0, sizeof(inStack)); 25 memset(indeg, 0, sizeof(indeg)); 26 memset(outdeg, 0, sizeof(outdeg)); 27 } 28 29 void tarjan(int u){ 30 dfn[u] = low[u] = ++clock; 31 S.push(u); 32 inStack[u] = 1; 33 for(int i=0; i<G[u].size(); i++){ 34 int v = G[u][i]; 35 if(!dfn[v]){ 36 tarjan(v); 37 low[u] = min(low[u], low[v]); 38 }else if(inStack[v]){ 39 low[u] = min(low[u], dfn[v]); 40 } 41 } 42 if(dfn[u] == low[u]){ 43 int v; 44 do{ 45 v = S.top(); 46 S.pop(); 47 inStack[v] = 0; 48 belong[v] = scc; 49 //printf("%d ", v); 50 }while(v != u); 51 scc++; 52 } 53 } 54 55 56 int main() 57 { 58 freopen("1236.txt", "r", stdin); 59 scanf("%d", &n); 60 for(int i=1; i<=n; i++){ 61 int u; 62 while(scanf("%d", &u) && u){ 63 G[i].push_back(u); 64 //outdeg[i]++; 65 //indeg[u]++; 66 } 67 } 68 init(); 69 for(int i=1; i<=n; i++){//遍历所有点 70 if(!dfn[i]){//未被发现的点 71 tarjan(i); 72 } 73 } 74 int a = 0; 75 int b = 0; 76 77 for(int i=1; i<=n; i++){//缩点 78 for(int j=0; j<G[i].size(); j++){ 79 int u = G[i][j]; 80 if(belong[i] != belong[u]){ 81 outdeg[belong[i]]++; 82 indeg[belong[u]]++; 83 } 84 } 85 } 86 87 for(int i=0; i<scc; i++){ 88 if(indeg[i] == 0) a++; 89 if(outdeg[i] == 0) b++; 90 } 91 92 b = max(a, b); 93 if(scc == 1) b = 0; 94 printf("%d\n%d\n", a, b); 95 return 0; 96 }
