强连通缩点学习小结-附加两个强连通缩点题poj2186、hdu2767

在学习了tarjan算法求解强连通分量之后就接触到强连通缩点，但是就是不知道怎么运用tarjan算法来找缩点，后来接触了几个有关缩点的题目，才了解到缩点的关键所在；

对于一个图，我们进行强连通分量求解之后，进行缩点操作，缩点的最大好处在于把一个杂乱无章的有向图变成一个有向无环图，而在有向无环图中，有两种点比较特殊：一种是入度为 0 的点，另一种是 出度为 0 的点。我们把入度为0的点就叫做根，出度为0的点叫做叶子，可以参见下图

对于图中的绿色点就是叶子，红色的点就是根，未标记的就是中间点，但是注意：这里是缩点之后形成的有向无环图，图中的每一个点就是一个强连通分量，那么我们怎么把一个图缩点成为一个有向无环图呢？那么这里就用到一个数组来“染色”，我们在求强连通分量的时候有一个 Bcnt 用来记录强连通分量个数，有一个数组Belong[MAX]来染色，Belong[i] =Bcnt 就表示 i 这个元素属于第Bcnt个强连通分量，在把所有的点求完强连通分量之后，我们只是得到一个所有点的归属数组Belong[MAX]，那么，之后我们就用两个数组 in[MAX],out[MAX]表示缩点后的有向无环图的点的入度和出度，用以下代码求解缩点形成的图

//125MS 1652K #include<stdio.h>#include<string.h>#define MAX 10001int n,m;//前向星struct Edge{int to,next;}edge[MAX*5];int head[MAX*2],tol;void add(int a,int b){edge[tol].to = b;edge[tol].next = head[a];head[a] = tol ++;}//tarjan算法int dfn[MAX*2],low[MAX*2],stack[MAX*2],Belong[MAX*2],time,top,Bcnt;bool instack[MAX*2];int in[MAX*2],out[MAX*2];//记录缩点后的入度出度void tarjan(int u){int v;dfn[u] = low[u] = ++time;stack[top ++] = u;instack[u] = true;for(int j = head[u] ; j != -1; j = edge[j].next){v = edge[j].to;if(!dfn[v]){tarjan(v);if(low[v] < low[u])low[u] = low[v];}else if(instack[v] && dfn[v] <low[u])low[u] = dfn[v];}if(dfn[u] == low[u]){Bcnt ++;do{v = stack[-- top];instack[v] = false;Belong[v] = Bcnt;}while(v != u);}}int main(){int a,b,i,j;int T;scanf("%d",&T);while(T --){scanf("%d%d",&n,&m);//建图tol = 0;memset(head,-1,sizeof(head));while(m --){scanf("%d%d",&a,&b);add(a,b);}//缩点Bcnt = time = top = 0;memset(dfn,0,sizeof(dfn));for(i = 1; i <= n; i ++)if(!dfn[i])tarjan(i);if(Bcnt == 1){printf("0\n");continue;}memset(in,0,sizeof(in));memset(out,0,sizeof(out));for(i = 1; i <= n; i ++){for(int k = head[i]; k != -1; k = edge[k].next){j = edge[k].to;if(Belong[i] != Belong[j])out[Belong[i]] ++, in[Belong[j]] ++;}}//缩点之后找叶子和根的数量int root = 0,leaf = 0;for(i = 1; i <= Bcnt; i ++){if(in[i] == 0) root ++;if(out[i] == 0) leaf ++;}printf("%d\n",leaf > root ? leaf : root);}return 0;}