运用Tarjan算法，求解图的点/边双连通分量。
1、点双连通分量【块】
割点可以存在多个块中，每个块包含当前节点u，分量以边的形式输出比较有意义。
typedef struct{ //栈结点结构 保存边
int front;
int rear;
}BNode;
BNode block_edge[MAXL];
int top; //栈指针,指向下一个空位
int num_block; //块计数
int b1,b2; //存储块中的边 辅助信息[全局变量]
void add(int *top,int front,int rear) //边入栈
{
if(*top < MAXL)
{
block_edge[*top].front=front;
block_edge[*top].rear=rear;
(*top)++;
}
}
void del(int *top) //边出栈
{
if(*top > )
{
(*top)--;
b1=block_edge[*top].front;
b2=block_edge[*top].rear;
}
}
void init_dfnlow(void) //初始化
{
depth=;
root=; //【**可自定义**】若不输出割点，可以不用
num_block=;
for(int i=;i<ALG->n;i++)
{
vis[i]=;
dfn[i]=low[i]=-;
}
top=;
b1=b2=-;
for(int j=;j<ALG->e;j++)
{
block_edge[j].front=;
block_edge[j].rear =;
}
}
void cutblock_Tarjan(int u,int parent)
{
int son;
ENode *ptr=(ENode *)malloc(sizeof(ENode));
dfn[u]=low[u]=depth++;
vis[u]=;
ptr=ALG->vlist[u].firstedge;
while(ptr!=NULL)
{
son=ptr->key;
if(son!=parent && dfn[son]<dfn[u]) //非树边&&回退边
{ // 新边压栈,v!=w是防止重复计算无向图中同一条树边
add(&top,u,son); //dfn[w]<dfn[u] 是防止重复计算回退边
if(!vis[son])
{
cutblock_Tarjan(son,u);
low[u]=MIN(low[u],low[son]);
if(low[son] >= dfn[u]) //u是割点,输出连通分支，包括(u,son)
{
num_block++;
do{
del(&top);
printf("<%c,%c> ",ALG->vlist[b1].vertex,ALG->vlist[b2].vertex);
}while(!(u==b1 && son==b2));
printf("\n");
/* del(&top); //两种不同的输出形式
while(!((u==b1) && (son==b2)))
{
printf("<%c,%c>,",ALG->vlist[b1].vertex,ALG->vlist[b2].vertex);
del(&top);
}
printf("<%c,%c>\n",ALG->vlist[u].vertex,ALG->vlist[son].vertex); */
}
}
else if(son != parent)
{
low[u]=MIN(low[u],dfn[son]);
}
}
ptr=ptr->next;
}
}
2、边双连通分量【缩点】
某一个点只能在一个“缩点”内，“缩点”时不包括当前节点u，分量以顶点的形式输出。
int stack[MAXL]; //栈用于缓存缩点,存放编号
int top;
int bnode[MAXL]; //用于存储缩点，存放编号
int count_bnodeele; //分量元素计数
void init_Tarjan(void)
{
depth=;
num_bridge=;
for(int i=;i<ALG->n;i++)
{
dfn[i]=low[i]=-;
vis[i]=;
// bridge[i]=0;
stack[i]=-;
}
top=;
} void init_bnode(void) //缩点初始化
{
count_bnodeele=;
for(int i=;i<ALG->n;i++)
bnode[i]=-;
} void bridge_node_Tarjan(int u,int parent)
{
int son;
ENode *ptr=(ENode*)malloc(sizeof(ENode)); dfn[u]=low[u]=depth++; //访问+标记+入栈+遍历
vis[u]=;
stack[top++]=u;
ptr=ALG->vlist[u].firstedge;
while(ptr!=NULL)
{
son=ptr->key;
if(son!=parent && dfn[son]<dfn[u])
{
if(!vis[son])
{
bridge_node_Tarjan(son,u);
low[u]=MIN(low[u],low[son]);
if(low[son] > dfn[u]) //(u,son)是桥
{
num_bridge++;
init_bnode(); //缩点初始化
while(stack[--top] != son)
{
bnode[count_bnodeele++]=stack[top];
}
bnode[count_bnodeele]=stack[top]; for(int cn=;cn<=count_bnodeele;cn++) //缩点输出
printf("%c ",ALG->vlist[bnode[cn]].vertex);
printf("\n");
}
}
else if(son != parent)
{
low[u]=MIN(low[u],dfn[son]);
}
}
ptr=ptr->next;
}
}
while(top != ) //最后节点无法全部出栈,被自然分成一个连通分量【***此步必须要有***】
{
top--;
printf("%c ",ALG->vlist[stack[top]].vertex);
}
printf("\n");