【笔记】判环
整理一下主流且比较好写的两种方法:
一、Tarjan(有无向图都推荐这种写法)
有向图就用强连通分量,无向图的话同样魔改一下:每一条边不能反着再走一遍。
有向图:
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=1e4+5,M=1e5+5;
struct node{ int v,ne; }e[M<<1];
int first[N],idx=0,dfn[N],low[N],n,m,scc[N],sum=0,num=0,cnt=0;
bool instk[N];
stack<int> stk;
inline void add(int x,int y){ e[++idx]=(node){y,first[x]}; first[x]=idx; }
inline void dfs(int u,int f){
dfn[u]=low[u]=++cnt; instk[u]=1; stk.push(u);
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v;
if(!dfn[v]) dfs(v,u),low[u]=min(low[u],low[v]);
else if(instk[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
int x; ++num;
do{
x=stk.top();
scc[x]=num;
instk[x]=0;
stk.pop();
}while(x!=u);
++sum;
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m; int u,v;
F(i,1,m) cin>>u>>v,add(u,v);
F(i,1,n) if(!dfn[i]) dfs(i,0);
cout<<sum<<'\n';
F(i,1,n) cout<<scc[i]<<' ';
return 0;
}
无向图:
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=1e4+5,M=1e5+5;
struct node{ int v,ne; }e[M<<1];
int first[N],idx=0,dfn[N],low[N],n,m,huan[N],sum=0,num=0,cnt=0;
bool instk[N];
stack<int> stk;
inline void add(int x,int y){ e[++idx]=(node){y,first[x]}; first[x]=idx; }
inline void dfs(int u,int f){
dfn[u]=low[u]=++cnt; instk[u]=1; stk.push(u);
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v; if(v==f) continue;
if(!dfn[v]) dfs(v,u),low[u]=min(low[u],low[v]);
else if(instk[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
int x,sz=0; ++num;
do{
x=stk.top();
huan[x]=num;
instk[x]=0;
++sz;
stk.pop();
}while(x!=u);
if(sz>1) ++sum;
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m; int u,v;
F(i,1,m) cin>>u>>v,add(u,v),add(v,u);
F(i,1,n) if(!dfn[i]) dfs(i,0);
cout<<sum<<'\n';
F(i,1,n) cout<<huan[i]<<' ';
return 0;
}
二、Topsort
注意topsort一遍之后的图上得每一个点不一定都在环上。
简单来说,topsort 只能去掉进环的所有点和边,而不能去掉出环的点和边。
怎么解决能,此时就可以类似染色的标记每一个点,如果当前点或它的儿子继续往下走能遇到一个已经染过色的点的话,那它就真的在环上。否则不在。
有向图就是先 topsort ,再依次访问每个块,并标记真正在环上的点。
无向图的话魔改一下 topsort:改为“每次将入度为1的点加入队列中”。并且 dfs 时不允许 v 沿着来时的反边走回 u.
有向图:
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=1e4+5,M=2e5+5;
struct node{ int v,ne;}e[M<<1];
int first[N],huan[N],in[N],idx=0,n,m,num=0;
bool vis[N];
inline void add(int x,int y){ e[++idx]=(node){y,first[x]}; first[x]=idx; }
inline void topsort(){
queue<int>q;
F(i,1,n) if(!in[i]) q.push(i);
while(q.size()){
int u=q.front(); q.pop(); vis[u]=1;
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v;
if(!(--in[v])) q.push(v);
}
}
}
inline void dfs(int u){
vis[u]=1; int rp=0;
for(int i=first[u];i;i=e[i].ne) {
int v=e[i].v;
if(!vis[v]) {
dfs(v);
if(!huan[u] && huan[v]) huan[u]=huan[v];
//注意不能直接huan[u]=huan[v]
//只要任意一个u的儿子在当前环上,那么u就在环上
}
else huan[u]=num;
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int u,v;
cin>>n>>m; F(i,1,m) cin>>u>>v,add(u,v),++in[v];
topsort();
F(i,1,n) if(!vis[i]) ++num,dfs(i);
F(i,1,n) if(!huan[i]) huan[i]=++num;
F(i,1,n) cout<<huan[i]<<' ';
return 0;
}
无向图:
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=1e4+5,M=2e5+5;
struct node{ int v,ne;}e[M<<1];
int first[N],huan[N],in[N],idx=0,n,m,num=0;
bool vis[N];
inline void add(int x,int y){ e[++idx]=(node){y,first[x]}; first[x]=idx; }
inline void topsort(){
queue<int>q;
F(i,1,n) if(in[i]==1) q.push(i);
while(q.size()){
int u=q.front(); q.pop(); vis[u]=1;
for(int i=first[u];i;i=e[i].ne){
int v=e[i].v;
if(--in[v]==1) q.push(v);//区别1
}
}
}
inline void dfs(int u,int f){
vis[u]=1; int rp=0;
for(int i=first[u];i;i=e[i].ne) {
int v=e[i].v; if(v==f) continue;//区别2
if(!vis[v]) {
dfs(v,u);
if(!huan[u] && huan[v]) huan[u]=huan[v];
//注意不能直接huan[u]=huan[v]
//只要任意一个u的儿子在当前环上,那么u就在环上
}
else huan[u]=num;
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int u,v;
cin>>n>>m; F(i,1,m) cin>>u>>v,add(u,v),add(v,u),++in[v],++in[u];
topsort();
F(i,1,n) if(!vis[i]) ++num,dfs(i,0);
F(i,1,n) if(!huan[i]) huan[i]=++num;
F(i,1,n) cout<<huan[i]<<' ';
return 0;
}
标签:判环,dfs,int,cin,笔记,++,low,huan
From: https://www.cnblogs.com/superl61/p/17834576.html