图算法强联通分量

2024-04-21 00:32

文章标签 算法分量联通

本文主要是介绍图算法强联通分量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDOJ 链接：迷宫城堡
CCF OJ链接：高速公路如果无法打开，请在 ccf 官网查找“高速公路”
参考博客：全网最!详!细!tarjan算法讲解

算法流程

初始化：now[cur]=low[cur]=当前索引
循环：对cur结点的所有邻接结点进行遍历
　　如果未访问：
　　　　DFS
　　　　用子结点的low[to]更新自己
　　如果已访问：并且遍历的后继包含在栈中：
　　　　用子结点的now[to]更新自己
对后继结点的遍历结束
如果当前结点now[cur]==low[cur]
　　不断出栈（出栈元素即为一个强联通分量），直到当前结点出栈

高速公路

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>#define I scanf
#define OL puts
#define O printf
#define F(a,b,c) for(a=b;a<c;a++)
#define FF(a,b) for(a=0;a<b;a++)
#define FG(a,b) for(a=b-1;a>=0;a--)
#define LEN 100010
#define MAX 0x06FFFFFF
#define V vector<int>using namespace std;struct edge{int to,next;
}mp[LEN*2]; //边表 
int head[LEN*2];//顶点u出发的第一条边
int cnt=0;  //边表索引 
void add (int u,int v){mp[cnt].to=v;mp[cnt].next=head[u];   //指针向前head[u]=cnt++;          //边表索引增加 
}int N,M;
int dfn[LEN];   //时间戳 
int low[LEN];
int visit[LEN]; //是否在栈中 
int Index=0;    //时间戳序号 
int Stack[LEN];
int top=0;//栈顶 
int ans_cnt=0;void tarjan(int x){dfn[x]=low[x]=++Index; //设置时间戳Stack[++top]=x; //当前结点进栈 visit[x]=1;     //标记结点在栈中for(int i=head[x];~i;i=mp[i].next) {//遍历当前结点的所有后继 int to=mp[i].to;if(dfn[to]==0){ //如果后继未访问 tarjan(to); //开始递归//递归结束，现在是栈底low[x] =min(low[x],low[to]);//用子结点的“最小时间戳”更新自己的“最小时间戳” }else if(visit[to]){//后继已经访问，并且在栈中 low[x] =min(low[x],dfn[to]);//用后继的“时间戳”更新自己的“最小时间戳” }}//对后继的遍历结束了if(low[x]==dfn[x]) {    //x结点是强联通分量子树的最小结点 int sum=0;do{sum++;int u=Stack[top];
//          cout<<u<<' ';visit[u]=0;top--;}while(x!=Stack[top+1]);
//      cout<<endl;ans_cnt+= (sum * (sum - 1)) / 2;//C(n,2)组合数 }
}void init(){memset(head,-1,sizeof head);
}int main(){
//    freopen("高速公路.txt","r",stdin);init();int i,a,b;I("%d%d",&N,&M);FF(i,M){I("%d%d",&a,&b);add(a,b);}for(i=1;i<=N;i++) if(dfn[i]==0) {tarjan(i);}O("%d\n",ans_cnt);return 0;
}