深圳网站制作公司咨询,唯品会网站建设特色,长春做网站团队,外发加工网接单文章目录割点代码桥点双连通分量代码边双连通分量代码割点
和强连通分量十分相似 分为树枝边、前向边和后向边 注意#xff01;
if(x!rlow[to]dfn[x]) cut[x]1;这句判断只能在树枝边出现 否则会因为前向边的存在而出错
代码
#includebits/stdc.h
us…
文章目录割点代码桥点双连通分量代码边双连通分量代码割点
和强连通分量十分相似 分为树枝边、前向边和后向边 注意
if(x!rlow[to]dfn[x]) cut[x]1;这句判断只能在树枝边出现 否则会因为前向边的存在而出错
代码
#includebits/stdc.h
using namespace std;
#define ll long long
int n,m;
const int N1e6100;
struct node{int to,nxt;
}p[2*N];
int fi[N],cnt-1;
void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;
}int r;
int dfn[N],t,low[N],cut[N];
void tj(int x){dfn[x]low[x]t;int num0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(!dfn[to]){
// printf(x%d to%d\n,x,to);tj(to);low[x]min(low[x],low[to]);if(x!rlow[to]dfn[x]) cut[x]1;num;}low[x]min(low[x],dfn[to]);}if(xrnum1) cut[x]1;return;
}
int main(){memset(fi,-1,sizeof(fi));scanf(%d%d,n,m);int a,b,c;for(int i1;im;i){scanf(%d%d,a,b);addline(a,b);addline(b,a); }for(int i1;in;i){ri;if(!dfn[i]) tj(i);}int ans0;for(int i1;in;i){if(cut[i]){ans;}}printf(%d\n,ans);for(int i1;in;i){if(cut[i]){printf(%d ,i);}}return 0;
}桥
也是类似的tarjan求法 但是需要注意:
树枝边需要直接跳过判断的条件是lowtodfnxlow_{to} dfn_xlowtodfnx不带等
仔细想想都是有道理的 2.是因为子树如果有连回x的边那么当前边也不是割边 1.是为了2服务的
void tarjan(int x){dfn[x]low[x]tim;for(int ifi[x];~i;ip[i].nxt){if(i(from[x]^1)) continue;int top[i].to;//printf( x%d to%d\n,x,to);if(!dfn[to]){from[to]i;tarjan(to);low[x]min(low[x],low[to]);if(low[to]dfn[x]) ans;}low[x]min(low[x],dfn[to]);}
}点双连通分量 定义点连通度1的极大子图 考虑建一个栈 把所有的前向边和树枝边压入栈中 每次通过dfnxlowtodfn_xlow_{to}dfnxlowto判断x是隔点时就把栈里(u,v)(u,v)(u,v)及上面的边全部弹出他们相连的点组成一个点双连通分量 找分量的好方法dfs
代码
洛谷P3225
#includebits/stdc.h
using namespace std;
#define ll long long
const int N2e3100;
const double eps1e-6;
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return f*x;
}
int n,m;
int ans;
struct node{int to,nxt,from;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){//printf(%d-%d w%d\n,x,y,w);p[cnt](node){y,fi[x],x};fi[x]cnt;
}
int dfn[N],low[N],zhan[N],tim,top,cut[N],r,tot;
void tarjan(int x){dfn[x]low[x]tim;zhan[top]x;int nm0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;//printf(x%d to%d\n,x,to);if(!dfn[to]){nm;tarjan(to);if(low[to]dfn[x]){cut[x]1;}low[x]min(low[x],low[to]);}else low[x]min(low[x],dfn[to]);}if(xr) cut[x]nm1;
}
int num,Cut,tag[N],t;
bool vis[N];
void dfs(int x){if(vis[x]||tag[x]t) return;num;//printf(x%d\n,x);if(cut[x]){tag[x]t;Cut;return;}vis[x]1;for(int ifi[x];~i;ip[i].nxt){int top[i].to;dfs(to);}
}
int main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifint o0;while(1){memset(fi,-1,sizeof(fi));cnt-1;memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));tim0;top0;memset(cut,0,sizeof(cut));memset(tag,0,sizeof(tag));mread();n0;if(!m) return 0;for(int i1;im;i){int xread(),yread();addline(x,y);addline(y,x);nmax(n,max(x,y));}totn;for(int i1;in;i){ri;if(!dfn[i]) tarjan(i);}ll nm0,ans1;for(int i1;in;i){//printf(i%d cut%d\n,i,cut[i]);if(!vis[i]!cut[i]){num0;Cut0;ti;dfs(i);printf(i%d num%d Cut%d\n,i,num,Cut);if(Cut0){nm2;ans*num*(num-1)/2;}else if(Cut1){nm;ans*(num-1);}}}printf(Case %d: %lld %lld\n,o,nm,ans);}
}
边双连通分量 定义边连通度1的极大子图 把桥求出后去掉 剩下的连通块就是边双连通分量 加边使图边双连通的方法把所有桥连回去形成一个树。设树度数为1的点的数量为xxx 若x1不用加边 否则加边数为(x1)/2(x1)/2(x1)/2
代码
洛谷P2860
#includebits/stdc.h
using namespace std;
#define ll long long
const int N5e5100;
const double eps1e-6;
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return f*x;
}
int n,m;
int ans;
struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){//printf(%d-%d w%d\n,x,y,w);p[cnt](node){y,fi[x]};fi[x]cnt;
}
int low[N],dfn[N],tim,from[N],cut[N],du[N];
int fa[N];
inline int find(int x){return fa[x]x?x:fa[x]find(fa[x]);
}
inline void merge(int x,int y){xfind(x),yfind(y);fa[x]y;return;
}
void tarjan(int x){dfn[x]low[x]tim;for(int ifi[x];~i;ip[i].nxt){//printf( x%d to%d\n,x,p[i].to);if(i(from[x]^1)) continue;int top[i].to;//printf( x%d to%d\n,x,to);if(!dfn[to]){from[to]i;tarjan(to);low[x]min(low[x],low[to]);if(low[to]dfn[x]){cut[i]2;cut[i^1]1;}}low[x]min(low[x],dfn[to]);}//printf(x%d dfn%d low%d\n,x,dfn[x],low[x]);
}
int main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifmemset(fi,-1,sizeof(fi));cnt1;nread();mread();for(int i1;im;i){int xread(),yread();addline(x,y);addline(y,x);}for(int i1;in;i){if(!dfn[i]) tarjan(i);}for(int i1;in;i){fa[i]i;}for(int x1;xn;x){for(int ifi[x];~i;ip[i].nxt){if(cut[i]) continue;merge(x,p[i].to);}}for(int x1;xn;x){int xxfind(x);for(int ifi[x];~i;ip[i].nxt){if(cut[i]!2) continue;int yyfind(p[i].to);du[xx];du[yy];}}for(int i1;in;i){if(find(i)idu[i]1) ans;}printf(%d\n,ans1?0:(ans1)/2);
}
/*
3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0
*/
