Tarjan算法
Tarjan算法是用于求图上的强连通分量(环)的算法。
应用：
- 有向图求强连通分量/缩点
- 无向图求割点
- 无向图找环
求强连通分量/缩点
强连通是有向图才有的概念。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。求有向图的强连通分量是Tarjan最基本的应用。
算法原理：
Tarjan算法的复杂度是O(v+e)的，因为只需要进行一次dfs就能处理出一个块中所有的强连通分量。首先建立dfn[]数组和low[]数组，前者记录节点的dfs序(第几个被dfs到)，确定后就不会改变，后者记录该节点属于的强连通分量(能遍历到的点)中dfs序最小的节点(的dfs序)，是会不断更新的。申明一个栈，用于存储可能成为强连通分量中的点。
然后，依次对每个节点进行dfs(因为从一个节点不一定能遍历到其他所有的节点)，初始化low[]为dfs序(low[u]=dfn[u]=dfsid)，将每次dfs的点u加入栈中，遍历这个点能到达的相邻的点v，如果这个点在栈中，说明构成了一个环，也就是强连通分量，就用v点的dfs序更新(取min)low[u]，当递归回溯时，所有强连通分量中的点low[]值都会被更新为dfn[v]。当一个点u的low[]值与它的dfs序相同时，说明这个点是一个强连通分量的根(也可能这个分量只有这一个点)，将栈中的点逐个弹出，直至u(也弹出)为止，将这些点染成同个颜色。
缩点：对于有些有向图上的问题，可以将一个强连通分量用一个点来等效替代，这个时候染成的一种颜色就是新图上的一个点。
int vis[maxn];//记录栈中的元素
int cnt[maxn];//记录一个强连通分量中的结点个数
int color[maxn];//染色，将同一个强连通分量中的点染成同个颜色
int dfn[maxn],low[maxn],dfsid=0,id=0;
stack<int>st;
void tarjan(int u){
low[u]=dfn[u]=++dfsid;
vis[u]=1;
st.push(u);
for(int i=head[u];i>0;i=E[i].next){
int v=E[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){//u是一个强连通分量的根
id++;
int k;
do{
k=st.top();st.pop();
vis[k]=0;
color[k]=id;
cnt[id]++;
}while(k!=u);
}
}
int main(){
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
}
无向图求割点
割点是无向图才有的概念。如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割集。若一个割集只有一个点，则称这个点为割点。
算法原理：
设u为dfs中的非根结点，如果点u的子结点v(后遍历到的点)能遍历到的最小 dfs序>=dfn[u]，那么删除u后v将和u之前的点断开，说明u是割点 。虽然是无向图，但这里的遍历是有方向的，一个点不能沿着已经访问过的点继续往前(根)遍历，但是low[]值能被所有相邻点更新。最后得到的low[]并不是正确的(能访问到的最小dfs序)，因为后续结点被限制在只能遍历到已访问过的点就停止了，因此判断的时候用low[v]==dfn[u]其实也是可以的。
若u是dfs中的根结点，那么如果u有2个及以上的儿子(除去u之外的每个连通块都是一个儿子)，u是割点。
#include <bits/stdc++.h>
using namespace std;
const int maxm=1e6+5;
const int maxn=1e5+5;
struct edge{
int v,next;
}E[maxm];
int head[maxn],tot=0;
void addedge(int u,int v){
E[++tot].v=v;
E[tot].next=head[u];
head[u]=tot;
}
set<int>res;//一定要用set，因为两种判割点方式可能会重复记录一个点
int low[maxn],dfn[maxn],dfsid;
void tarjan(int u,int rt){
low[u]=dfn[u]=++dfsid;
int child=0;
for(int i=head[u];i>0;i=E[i].next){
int v=E[i].v;
if(!dfn[v]){
child++;
tarjan(v,rt);
low[u]=min(low[u],low[v]);
if(u!=rt&&low[v]>=dfn[u]){
res.insert(u);
}
}
low[u]=min(low[u],dfn[v]);
}
if(u==rt&&child>1)
res.insert(u);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i,i);
printf("%d
",res.size());
for(auto v:res){
printf("%d ",v);
}
printf("
");
}
仙人掌图判断&判环
定义(有向图和无向图略有不同)
有向图:
- 是一个强连通图
- 每条有向边都属于且仅属于一个环(强连通图所有边都必须在环上)
无向图:
- 是一个连通图
- 每条无向边至多属于一个环（即有些无向边可以不属于任何一个环）
无向图仙人掌的判定和环计数:
首先判断一个图是否是连通的，dfs一次判断点的个数即可，之后每找到一个环，就将环上除了根(最先遍历到的点)之外的点度数都+1，如果一个点度数为2，说明这个点的前向边被两个环所共有，即该图不是仙人掌图。
//洛谷P4129，ans需要改成大数
#include <bits/stdc++.h>
using namespace std;
const int maxm=1e6+5;
const int maxn=1e5+5;
struct edge{
int v,next;
}E[maxm];
int head[maxn],tot=0;
void addedge(int u,int v){
E[++tot].v=v;
E[tot].next=head[u];
head[u]=tot;
}
int dfn[maxn],dep[maxn],fa[maxn],dfsid=0;
int cnt[maxn];//记录一条边属于环的个数
long long ans=1;
bool cal(int u,int rt){
ans=ans*(dep[u]-dep[rt]+2);//dep[u]-dep[rt]+1为环的大小
for(u;u!=rt;u=fa[u]){//这里用点来代替dfs树边
if(++cnt[u]==2)return 0;//如果一个边被两个环共用，那么不是仙人掌图
}
return 1;
}
int siz=0;
int ok=1;
void tarjan(int u){
siz++;
dfn[u]=++dfsid;
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v==fa[u])continue;
if(!dfn[v]){
dep[v]=dep[u]+1;
fa[v]=u;
tarjan(v);
}
}
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(fa[v]!=u&&dfn[u]<dfn[v]){
if(!cal(v,u))
ok=0;
}
}
}
int a[maxn];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int ki;
scanf("%d",&ki);
for(int i=1;i<=ki;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=ki-1;i++){
addedge(a[i],a[i+1]);
addedge(a[i+1],a[i]);
}
}
tarjan(1);
if(ok==0||siz!=n){//边被多个环共用||非连通图
printf("0
");
}
else{
cout<<ans<<endl;//所有环大小+1的乘积
}
}
有向图仙人掌的判定:
先用tarjan判断这个图是否强连通，之后同无向图一样，找是否有度数为2的点。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxm=1e6+5;
struct edge{
int v,next;
}E[maxm];
int head[maxn],tot=0;
void addedge(int u,int v){
E[++tot].v=v;
E[tot].next=head[u];
head[u]=tot;
}
int vis[maxn];//记录栈中的元素
int dfn[maxn],low[maxn],fa[maxn],dfsid=0,id=0;
stack<int>st;
int siz=0;
void tarjan(int u){
siz++;
low[u]=dfn[u]=++dfsid;
vis[u]=1;
st.push(u);
for(int i=head[u];i>0;i=E[i].next){
int v=E[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){//u是一个强连通分量的根
id++;
int k;
do{
k=st.top();st.pop();
vis[k]=0;
}while(k!=u);
}
}
int du[maxn];
bool cal(int u,int rt){
for(u;u!=rt;u=fa[u]){
if(++du[u]==2){
return 0;
}
}
return 1;
}
int ok=1;
void dfs(int u){
dfn[u]=++id;
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(!dfn[v]){
fa[v]=u;
dfs(v);
}
else{
if(!cal(u,v)){
ok=0;
}
}
}
}
void init(int n){
dfsid=0;id=0;
fill(dfn,dfn+1+n,0);
fill(low,low+1+n,0);
fill(fa,fa+1+n,0);
fill(du,du+1+n,0);
fill(vis,vis+1+n,0);
siz=0;ok=1;
}
int main(){
int T;
cin>>T;
while(T--){
int n;
scanf("%d",&n);
init(n);
fill(head,head+1+n,0);
tot=0;
int u,v;
while(scanf("%d%d",&u,&v)){
if(u==0&&v==0) break;
u++;v++;
addedge(u,v);
}
tarjan(1);
if(id>1||siz!=n){
printf("NO
");
continue;
}
init(n);
dfs(1);
if(!ok){
printf("NO
");
}
else{
printf("YES
");
}
}
}
例题
Bomb(缩点/拓扑)
题意：
一个平面上有n个炸弹，每个炸弹i有一个圆形的爆炸范围ri和二维坐标xi,yi，以及手动引爆这个炸弹的费用ci。如果引爆了一个炸弹，其爆炸范围内(包括边界)的所有其他炸弹都会被引爆(会发生连锁反应)，问如何以最小的费用引爆所有的炸弹？
思路:
显然一个炸弹能引爆其他炸弹，但是其他炸弹不一定能引爆这个炸弹，这是一个有向图。但是有的炸弹可能会循环引爆构成一个环，用tarjan将图上的环缩掉就可以变成一个森林图，显然只要把图中所有入度为0节点引爆，所有点都会被引爆。
缩点后，计算入度前要判断该边连接的两个点u,v是否为同一颜色，同色就不计度数，不同颜色就将v所在颜色的入度+1。同样地，计算一个大点的权值也是用小点对该颜色的权值取min。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+5;
const int maxm=2e6+5;
struct edge{
int v,next;
}E[maxm];
int tot=0,head[maxn];
void addedge(int u,int v){
E[++tot].v=v;
E[tot].next=head[u];
head[u]=tot;
}
int vis[maxn];//记录栈中的元素
int cnt[maxn];//记录一个强连通分量中的结点个数
int color[maxn];//染色，将同一个强连通分量中的点染成同个颜色
int dfn[maxn],low[maxn],dfsid=0,id=0;
int n;
stack<int>st;
void tarjan(int u){
low[u]=dfn[u]=++dfsid;
vis[u]=1;
st.push(u);
for(int i=head[u];i>0;i=E[i].next){
int v=E[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){//u是一个强连通分量的根
id++;
int k;
do{
k=st.top();st.pop();
vis[k]=0;
color[k]=id;
cnt[id]++;
}while(k!=u);
}
}
int x[maxn],y[maxn],r[maxn],c[maxn];
bool f(ll x1,ll y1,ll r1,ll x2,ll y2){
if((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<=r1*r1)
return 1;
else return 0;
}
int du[maxn];//入度
int cost[maxn];
void init(){
memset(cost,0,sizeof(cost));
memset(du,0,sizeof(du));
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
dfsid=0,id=0;
tot=0;
while(st.size())st.pop();
}
int main(){
int t;
cin>>t;
for(int kase=1;kase<=t;kase++){
scanf("%d",&n);
init();
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&x[i],&y[i],&r[i],&c[i]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(j==i)continue;
if(f(x[i],y[i],r[i],x[j],y[j])){
addedge(i,j);
}
}
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int u=1;u<=n;u++){
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(color[v]!=color[u]){
du[color[v]]++;//记录缩成的大点的入度
}
}
}
for(int i=1;i<=n;i++){
if(cost[color[i]]==0){
cost[color[i]]=c[i];
}
else
cost[color[i]]=min(cost[color[i]],c[i]);
}
int ans=0;
for(int i=1;i<=id;i++){
if(du[i]==0)
ans+=cost[i];
}
printf("Case #%d: %d
",kase,ans);
}
}