运用Tarjan算法，求解图的点/边双连通分量。
1、点双连通分量【块】
割点可以存在多个块中，每个块包含当前节点u，分量以边的形式输出比较有意义。
1 typedef struct{ //栈结点结构 保存边 2 int front; 3 int rear; 4 }BNode; 5 BNode block_edge[MAXL]; 6 int top; //栈指针,指向下一个空位 7 int num_block; //块计数 8 int b1,b2; //存储块中的边 辅助信息[全局变量] 9 void add(int *top,int front,int rear) //边入栈 10 { 11 if(*top < MAXL) 12 { 13 block_edge[*top].front=front; 14 block_edge[*top].rear=rear; 15 (*top)++; 16 } 17 } 18 void del(int *top) //边出栈 19 { 20 if(*top > 0) 21 { 22 (*top)--; 23 b1=block_edge[*top].front; 24 b2=block_edge[*top].rear; 25 } 26 } 27 28 void init_dfnlow(void) //初始化 29 { 30 depth=0; 31 root=0; //【**可自定义**】若不输出割点，可以不用 32 num_block=0; 33 for(int i=0;i<ALG->n;i++) 34 { 35 vis[i]=0; 36 dfn[i]=low[i]=-1; 37 } 38 39 top=0; 40 b1=b2=-1; 41 for(int j=0;j<ALG->e;j++) 42 { 43 block_edge[j].front=0; 44 block_edge[j].rear =0; 45 } 46 } 47 48 void cutblock_Tarjan(int u,int parent) 49 { 50 int son; 51 ENode *ptr=(ENode *)malloc(sizeof(ENode)); 52 53 dfn[u]=low[u]=depth++; 54 vis[u]=1; 55 ptr=ALG->vlist[u].firstedge; 56 while(ptr!=NULL) 57 { 58 son=ptr->key; 59 if(son!=parent && dfn[son]<dfn[u]) //非树边&&回退边 60 { // 新边压栈,v!=w是防止重复计算无向图中同一条树边 61 add(&top,u,son); //dfn[w]<dfn[u] 是防止重复计算回退边 62 if(!vis[son]) 63 { 64 cutblock_Tarjan(son,u); 65 low[u]=MIN(low[u],low[son]); 66 if(low[son] >= dfn[u]) //u是割点,输出连通分支，包括(u,son) 67 { 68 num_block++; 69 do{ 70 del(&top); 71 printf("<%c,%c> ",ALG->vlist[b1].vertex,ALG->vlist[b2].vertex); 72 }while(!(u==b1 && son==b2)); 73 printf(" "); 74 75 /* del(&top); //两种不同的输出形式 76 while(!((u==b1) && (son==b2))) 77 { 78 printf("<%c,%c>,",ALG->vlist[b1].vertex,ALG->vlist[b2].vertex); 79 del(&top); 80 } 81 printf("<%c,%c> ",ALG->vlist[u].vertex,ALG->vlist[son].vertex); */ 82 } 83 } 84 else if(son != parent) 85 { 86 low[u]=MIN(low[u],dfn[son]); 87 } 88 } 89 90 ptr=ptr->next; 91 } 92 }
2、边双连通分量【缩点】
某一个点只能在一个“缩点”内，“缩点”时不包括当前节点u，分量以顶点的形式输出。
1 int stack[MAXL]; //栈用于缓存缩点,存放编号 2 int top; 3 int bnode[MAXL]; //用于存储缩点，存放编号 4 int count_bnodeele; //分量元素计数 5 void init_Tarjan(void) 6 { 7 depth=0; 8 num_bridge=0; 9 for(int i=0;i<ALG->n;i++) 10 { 11 dfn[i]=low[i]=-1; 12 vis[i]=0; 13 // bridge[i]=0; 14 stack[i]=-1; 15 } 16 top=0; 17 } 18 19 void init_bnode(void) //缩点初始化 20 { 21 count_bnodeele=0; 22 for(int i=0;i<ALG->n;i++) 23 bnode[i]=-1; 24 } 25 26 void bridge_node_Tarjan(int u,int parent) 27 { 28 int son; 29 ENode *ptr=(ENode*)malloc(sizeof(ENode)); 30 31 dfn[u]=low[u]=depth++; //访问+标记+入栈+遍历 32 vis[u]=1; 33 stack[top++]=u; 34 ptr=ALG->vlist[u].firstedge; 35 while(ptr!=NULL) 36 { 37 son=ptr->key; 38 if(son!=parent && dfn[son]<dfn[u]) 39 { 40 if(!vis[son]) 41 { 42 bridge_node_Tarjan(son,u); 43 low[u]=MIN(low[u],low[son]); 44 if(low[son] > dfn[u]) //(u,son)是桥 45 { 46 num_bridge++; 47 init_bnode(); //缩点初始化 48 while(stack[--top] != son) 49 { 50 bnode[count_bnodeele++]=stack[top]; 51 } 52 bnode[count_bnodeele]=stack[top]; 53 54 for(int cn=0;cn<=count_bnodeele;cn++) //缩点输出 55 printf("%c ",ALG->vlist[bnode[cn]].vertex); 56 printf(" "); 57 } 58 } 59 else if(son != parent) 60 { 61 low[u]=MIN(low[u],dfn[son]); 62 } 63 } 64 ptr=ptr->next; 65 } 66 } 67 while(top != 0) //最后节点无法全部出栈,被自然分成一个连通分量【***此步必须要有***】 68 { 69 top--; 70 printf("%c ",ALG->vlist[stack[top]].vertex); 71 } 72 printf(" ");