poj-1236-一行学习强连通分量

poj-1236-一起学习强连通分量

题目不是很好理解，简单说一下

就是有一个有向图，第一问求至少要复制几次软件，才能保证每个地方都有，实际上就是求入度为0的，也就是走不到的。第二问求至少添加几个扩展，也即是添加几条边，让无论从那个地方，都能让任何地方得到软件。也就是添加几条边，能让整个图强连通。

强连通分量算法1---kosaraju最好理解的两次dfs。

1. DFS有向图G，并以后根序记录节点

2. 把存在于记录集中且最后访问节点作为起点，DFS反图GT,并以先根序把节点从记录中剔除；

3. 若此次不能DFS反图GT所有节点，则重复步骤2，直到所有节点都被剔除出记录；每次剔除掉的节点集即为原有向图G的一个强连通分量

1. 第一次DFS有向图G时，最后记录下的节点必为最后一棵生成树的根节点。
证明：假设最后记录下节点不是树根，则必存在一节点为树根，且树根节点必为此节点祖先；而由后根序访问可知祖先节点比此节点更晚访问，矛盾；原命题成立

2. 第一次DFS的生成森林中，取两节点A、B，满足：B比A更晚记录下,且B不是A的祖先(即在第一次DFS中，A、B处于不同的生成树中)；则在第二次DFS的生成森林中，B不是A的祖先，且A也不是B的祖先(即在第二次DFS中，A、B处于不同的生成树中)。
证明：假设在第二次DFS的生成森林中，B是A的祖先，则反图GT中存在B到A路径，即第一次DFS生成森林中，A是B的祖先，则A必比B更晚记录下，矛盾；假设在第二次DFS的生成森林中，A是B的祖先，则反图GT中存在A到B路径，即第一次DFS生成森林中，B是A的祖先,矛盾；原命题成立

3. 按上述步骤求出的必为强连通分量
证明：首先，证明2保证了第二次DFS中的每一棵树都是第一次DFS中的某棵树或某棵树的子树。其次，对于第二次DFS中的每棵树，第一次DFS保证了从根到其子孙的连通性，第二次DFS保证了根到子孙的反向连通性(即子孙到根的连通性)；由此，此树中的每个节点都通过其根相互连通。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define nMax 110int map[nMax][nMax],mapT[nMax][nMax];int belong[nMax];int order[nMax];bool vist[nMax];int n,index,cnt;int indegree[nMax],outdegree[nMax];void firstDfs(int u)//第一次dfs，求出各点被搜索时的时间戳{vist[u] = true;for (int i = 1; i <= n; ++ i){if (map[u][i] && !vist[i]){firstDfs(i);}}order[++ index] = u;//记录每点被搜索时的时间戳//printf("%d\n", u);}void secondDfs(int u)//第二次dfs，找到每个强连通分量{vist[u] = true;belong[u] = cnt;//记录u点属于哪个强连通分量cntfor (int i = 1; i <= n; ++ i){if (!vist[i] && mapT[u][i]){secondDfs(i);}}}void kosaraju(){index = 0;cnt = 0;memset(vist, false, sizeof(vist));memset(order, 0, sizeof(order));for (int i = 1; i <= n; ++ i){if (!vist[i]){firstDfs(i);//dfs求各点时间戳}}memset(vist, false, sizeof(vist));for (int i = n; i >= 1; -- i)//倒着搜索找到各个强连通分量{if (!vist[order[i]]){cnt ++;//强连通分量的个数secondDfs(order[i]);}}}void output(){int inNum = 0,outNum = 0;memset(indegree, 0, sizeof(indegree));memset(outdegree, 0, sizeof(outdegree));for (int i = 1; i <= n; ++ i)//求强连通分量的出度和入度{for (int j = 1; j <= n; ++ j){if (map[i][j] && belong[i] != belong[j]){indegree[belong[j]] ++;outdegree[belong[i]] ++;}}}for (int i = 1; i <= cnt; ++ i)//求出出度和入度为0的点的个数{if (!indegree[i]){inNum ++;}if (!outdegree[i]){outNum ++;}}if (cnt == 1)//如果这个图强连通{printf("1\n0\n");}else//否则printf("%d\n%d\n",inNum, inNum > outNum ? inNum : outNum);}int main(){while (scanf("%d", &n) != EOF){memset(map, 0, sizeof(map));memset(mapT, 0, sizeof(mapT));for (int i = 1; i <= n; ++ i){int v;while (scanf("%d", &v) && v){map[i][v] = 1;//正向图邻接矩阵mapT[v][i] = 1;//逆向图邻接矩阵}}kosaraju();//kosaraju算法output();}return 0;}