- 点双联通的图：任意两条边都在同一个简单环中
- 边双联通的图：每条边都至少在一个简单环中
POJ1144 网络
description:
给出一张(N)个点的无向图，求其中割点的个数
data range:
(Nle 100)
solution:
一道模板题（但是读入实在是把我恶心坏了）
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#include<sstream>
using namespace std;
const int N=105;
int n,dfn[N],low[N],sign;
vector<int>e[N];
bool flag[N];
string s;
void dfs(int u,int fa)
{
low[u]=dfn[u]=++sign;
int cd=0;
for(int i=0;i<e[u].size();++i)
{
int v=e[u][i],&lu=low[u];
if(v==fa)continue;
if(!dfn[v])
{
dfs(v,u);lu=min(lu,low[v]);
if(low[v]>=dfn[u]&&u!=fa)flag[u]=1;
if(u==fa)++cd;
}
else lu=min(lu,dfn[v]);
}
if(u==fa&&cd>1)flag[u]=1;
}
int main()
{
while(1)
{
cin>>n;if(!n)break;
for(int i=1;i<=n;++i)e[i].clear();
while(1)
{
int u;cin>>u;if(!u)break;
getline(cin,s);stringstream ss(s);
int v;
while(ss>>v)
e[u].push_back(v),e[v].push_back(u);
}
fill(flag+1,flag+n+1,0);
fill(dfn+1,dfn+n+1,0);
fill(low+1,low+n+1,0);sign=0;
for(int i=1;i<=n;++i)if(!dfn[i])dfs(i,i);
printf("%d
",count(flag+1,flag+n+1,1));
}
return 0;
}
POJ2117 Electricity
description:
给定一张(N)个点的无向图，询问删除一个点后最多有多少个联通分量
data range:
(Nle 10^4)
solution:
还是比较模板
求割点时顺便统计下就行了
但要稍微注意下图不连通的情况
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e4+5;
int n,m,low[N],dfn[N],sign,ans;
vector<int>e[N];
void dfs(int u,int fa)
{
low[u]=dfn[u]=++sign;
int cd=u==fa?0:1;
for(int i=0;i<e[u].size();++i)
{
int v=e[u][i],&lu=low[u];
if(v==fa)continue;
if(!dfn[v])
{
dfs(v,u),lu=min(lu,low[v]);
if(u!=fa&&low[v]>=dfn[u])++cd;
else if(u==fa)++cd;
}
else lu=min(lu,dfn[v]);
}
ans=max(ans,cd);
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
if(!n&&!m)break;
for(int i=1;i<=n;++i)e[i].clear();
for(int i=1;i<=m;++i)
{
int u,v;scanf("%d%d",&u,&v);++u,++v;
e[u].push_back(v),e[v].push_back(u);
}
int cnt=0;sign=0,ans=0;
fill(dfn+1,dfn+n+1,0);
for(int i=1;i<=n;++i)
if(!dfn[i])++cnt,dfs(i,i);
printf("%d
",ans+cnt-1);
}
return 0;
}
HDU3749 Financial Crisis
description:
给出一个(N)个点的无向图，有(Q)次询问，每次询问给出两个点(u,v)，如果它们间没有路径，输出(zero)；否则如果它们间有至少两条点不重复的路径，输出(two or more);否则输出(one)
data range:
(Nle 5*10^3)
(Qle 10^3)
solution:
首先如果两个点不连通，那么输出(zero),这个可以用并查集来维护
注意到点不重复这四个字
那么如果有至少两条点不重复的路径，那么这两个点一定是在同一个点双联通分量内的
其他情况都输出(one)（注意两点一边的特殊情况）
p.s.这道题可以当做点双的一个完整模板
code:
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int N=5005;
int n,m,q,fa[N],dfn[N],low[N],sign,cnt,id[N],kase;
struct edge{int u,v;edge(int _u=0,int _v=0){u=_u,v=_v;}};
stack<edge>s;
vector<int>e[N],bcc[N],bccs[N];
int fd(int x){return fa[x]==x?x:fa[x]=fd(fa[x]);}
inline void merge(int u,int v){u=fd(u),v=fd(v);if(u!=v)fa[u]=v;}
inline void add(int u,int t)
{
if(id[u]==t)return;
id[u]=t;bcc[t].push_back(u),bccs[u].push_back(t);
}
void dfs(int u,int fa)
{
low[u]=dfn[u]=++sign;
for(int i=0;i<e[u].size();++i)
{
int v=e[u][i],&lu=low[u];
edge eg=edge(u,v);
if(v==fa)continue;
if(!dfn[v])
{
s.push(eg);
dfs(v,u),lu=min(lu,low[v]);
if(low[v]>=dfn[u])
{
++cnt;
while(1)
{
edge x=s.top();s.pop();
add(x.u,cnt),add(x.v,cnt);
if(x.u==u&&x.v==v)break;
}
}
}
else if(dfn[v]<dfn[u])
s.push(eg),lu=min(lu,dfn[v]);
}
}
inline int solve(int u,int v)
{
if(fd(u)!=fd(v))return 0;
vector<int>&bu=bccs[u],&bv=bccs[v];
for(int i=0;i<bu.size();++i)
for(int j=0;j<bv.size();++j)
if(bu[i]==bv[j]&&bcc[bu[i]].size()>2)return 2;
return 1;
}
int main()
{
while(scanf("%d%d%d",&n,&m,&q)==3)
{
if(!n&&!m&&!q)break;
for(int i=1;i<=n;++i)
e[i].clear(),bcc[i].clear(),bccs[i].clear(),fa[i]=i;
for(int i=1;i<=m;++i)
{
int u,v;scanf("%d%d",&u,&v);++u,++v;
e[u].push_back(v),e[v].push_back(u);
merge(u,v);
}
fill(dfn+1,dfn+n+1,0);sign=0;cnt=0;
fill(id+1,id+n+1,0);
for(int i=1;i<=n;++i)if(!dfn[i])dfs(i,i);
printf("Case %d:
",++kase);
while(q--)
{
int u,v;scanf("%d%d",&u,&v);u++,v++;
int ans=solve(u,v);
puts(ans?(ans==1?"one":"two or more"):"zero");
}
}
return 0;
}
HDU4587 TWO NODES
description:
给出一个(N)个点的无向图，询问删去其中两个点后最多可以将其分成多少个联通块
data range:
(Nle 5*10^3)
solution:
考虑到数据范围(Nle 5000)
因此我们可以先枚举其中一个被删除的点
然后在剩余的图上计算删去当前点后形成的联通块个数即可
还是注意下图不连通的情况
code:
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5005;
int n,m,cut,dfn[N],low[N],sign,ans,anss;
vector<int>e[N];
void dfs(int u,int fa)
{
low[u]=dfn[u]=++sign;
int cd=u==fa?0:1;
for(int i=0;i<e[u].size();++i)
{
int v=e[u][i],&lu=low[u];
if(v==fa||v==cut)continue;
if(!dfn[v])
{
dfs(v,u),lu=min(lu,low[v]);
if(low[v]>=dfn[u]&&u!=fa)++cd;
else if(u==fa)++cd;
}
else if(dfn[v]<dfn[u])lu=min(lu,dfn[v]);
}
ans=max(ans,cd);
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
for(int i=1;i<=n;++i)e[i].clear();
for(int i=1;i<=m;++i)
{
int u,v;scanf("%d%d",&u,&v);++u,++v;
e[u].push_back(v),e[v].push_back(u);
}
anss=0;
for(int i=1;i<=n;++i)
{
cut=i;sign=0;int cnt=0;ans=0;
fill(dfn+1,dfn+n+1,0);
for(int j=1;j<=n;++j)
if(j!=cut&&!dfn[j])++cnt,dfs(j,j);
anss=max(anss,ans+cnt-1);
}
printf("%d
",anss);
}
return 0;
}
POJ3177 分离的路径(USACO 2006 Jan. Gold)
description:
给出一个(N)个点(M)条边的无向图,询问至少新添加多少点后可以使得原图边双联通
data range:
(Nle 5000)
(Mle 10^4)
solution:
我们可以将原图的所有极大边双连通分量缩点
然后参考有向图添加尽量少的边使得整个图为强联通的做法
我们只要将缩点后所有度数为1的点两个一组地用一条边相连即可
形式化地，设度数为1的点有(x)个，那么就需要添加(lceil frac{x}{2}
ceil)条边
具体做法其实没有说的那么麻烦
直接在原图上找到左右的桥
然后再dfs一遍，强制不能经过桥，这样就可以找到所有的边双了
最后枚举每条边统计度数即可
#include<bits/stdc++.h>
using namespace std;
const int N=5005,M=2e4+5;
int n,m,tot=1,sign,cnt;
int fi[N],ne[M],to[M],dfn[N],low[N],id[N],deg[N];
bool flag[M];
inline void add(int x,int y){ne[++tot]=fi[x],fi[x]=tot,to[tot]=y;}
void dfs(int u,int fa)
{
low[u]=dfn[u]=++sign;
for(int i=fi[u];i;i=ne[i])
{
int v=to[i],&lu=low[u];
if(v==fa)continue;
if(!dfn[v])
{
dfs(v,u),lu=min(lu,low[v]);
if(low[v]>dfn[u])flag[i]=flag[i^1]=1;
}
else if(dfn[v]<dfn[u])lu=min(lu,dfn[v]);
}
}
void _dfs(int u,int col)
{
id[u]=col;
for(int i=fi[u];i;i=ne[i])
{
int v=to[i];
if(flag[i]||id[v])continue;
_dfs(v,col);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
int u,v;scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
for(int i=1;i<=n;++i)if(!dfn[i])dfs(i,i);
for(int i=1;i<=n;++i)if(!id[i])_dfs(i,++cnt);
for(int i=1;i<=n;++i)
for(int j=fi[i];j;j=ne[j])
if(id[i]!=id[to[j]])++deg[id[i]],++deg[id[to[j]]];
int ans=count(deg+1,deg+cnt+1,2);
printf("%d
",ans+1>>1);
return 0;
}
POJ3352 Road Construction
同上一道题
井下矿工 (Mining Your Own Business, WF2011, LA5135)
description:
在一个无向图上选择尽量少的点涂黑，使得删除任意一个点后，每个连通分量里都至少有一个黑点。
data range:
(Nle 5*10^4)
solution:
先求出所有的极大点双连通分量
对于每个点双连通分量单独考虑，设其大小为(sz)
如果其内部割点个数(>1)，那么不用在其内部涂黑（因为如果某个割点被删去后，还可以通过其他割点和别的联通分量形成联通块）
如果其内部割点个数(=1)，那么需要在一个不是割点的位置涂黑，方案数就是(sz-1)（即去除割点）
如果其内部割点个数(=0)，那么就需要在其中任选两个涂黑，方案数就是(sz*(sz-1)/2)（没有割点就相当于这个块是独立的，泡不到其他块，因此要选两个点）
另外还是要注意图不连通的情况
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int n,m,sign,cnt,low[N],dfn[N],id[N],fa[N],sz[N];
bool flag[N],pd[N];
vector<int>e[N],bcc[N];
int fd(int x){return fa[x]==x?x:fa[x]=fd(fa[x]);}
inline bool isnum(char &ch){return '0'<=ch&&ch<='9';}
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;!isnum(ch);ch=getchar())if(ch=='-')w=-1;
for(;isnum(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
inline void add(int u,int v)
{
if(id[u]==v)return;
id[u]=v,bcc[v].push_back(u);
}
int stx[N],sty[N],top;
void dfs(int u,int pr)
{
low[u]=dfn[u]=++sign;
int cd=0;
for(int i=0;i<e[u].size();++i)
{
int v=e[u][i];
if(v==pr)continue;
if(!dfn[v])
{
++cd;stx[++top]=u,sty[top]=v;
dfs(v,u),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
++cnt;flag[u]=1;
while(1)
{
add(stx[top],cnt),add(sty[top],cnt);
if(stx[top]==u&&sty[top]==v)break;--top;
}
--top;
}
}
else if(dfn[v]<dfn[u])
{
stx[++top]=u,sty[top]=v;
low[u]=min(low[u],dfn[v]);
}
}
if(u==pr&&cd<=1)flag[u]=0;
}
int main()
{
for(int kase=1;;++kase)
{
m=read();if(!m)break;n=0;
for(int i=1;i<=m+1;++i)fa[i]=i,sz[i]=1;
for(int i=1;i<=m;++i)
{
int u=read(),v=read();n=max(n,max(u,v));
e[u].push_back(v),e[v].push_back(u);
u=fd(u),v=fd(v);
if(u!=v)fa[u]=v,sz[v]+=sz[u];
}
for(int i=1;i<=n;++i)if(!dfn[i])dfs(i,i);
int ans1=0;ll ans2=1ll;
for(int i=1;i<=cnt;++i)
{
int num=0;
for(int j=0;j<bcc[i].size();++j)num+=flag[bcc[i][j]];
if(num==1)++ans1,ans2*=bcc[i].size()-1,pd[fd(bcc[i][0])]=1;
}
for(int i=1;i<=n;++i)
if(i==fd(i)&&!pd[i])
pd[i]=1,ans1+=min(sz[i],2),ans2*=sz[i]>1?1ll*sz[i]*(sz[i]-1)/2ll:1;
printf("Case %d: %d %lld
",kase,ans1,ans2);
for(int i=1;i<=n;++i)e[i].clear(),bcc[i].clear();
top=cnt=sign=0;fill(dfn+1,dfn+n+1,0);
fill(id+1,id+n+1,0);fill(flag+1,flag+n+1,0);
fill(pd+1,pd+n+1,0);
}
return 0;
}
HDU 3394 Railway
description:
给一个(N)个点的无向图，如果至少有两个环共用了一些边，那么这些边被认为是冲突边，如果一些边不在任何一个环中，这些边被认为是多余边，问这个图中有多少多余边和冲突边
data range:
(Nle 10^4)
solution:
对于多余边，直接在原图上找桥就可以了
以下考虑统计冲突边
对于每一个点双联通分量，不妨设其中点的个数为(cntp),边的个数为(cnte)
容易知道(cntple cnte)
如果(cntp==cnte)那么会恰好形成一个简单环
但如果(cntp<cnte),那么这个联通分量中所有边都是冲突边
上图是(cntp=cnte-1)的情况，容易发现其中已经有3个环
然后就是模板了
code:
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10005,M=1e5+5;
int n,m,tot=1,sign,ans1,ans2,cnt;
int fi[N],ne[M<<1],to[M<<1];
int dfn[N],low[N],vis[N];
bool flag[M<<1];
inline bool isnum(char &ch){return '0'<=ch&ch<='9';}
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;!isnum(ch);ch=getchar())if(ch=='-')w=-1;
for(;isnum(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
inline void add(int x,int y){ne[++tot]=fi[x],fi[x]=tot,to[tot]=y;}
int stx[M],sty[M],top;
void dfs(int u,int fa)
{
low[u]=dfn[u]=++sign;
for(int i=fi[u];i;i=ne[i])
{
int v=to[i];
if(v==fa)continue;
if(!dfn[v])
{
stx[++top]=u,sty[top]=v;
dfs(v,u),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
int cnte=0,cntp=0;
++cnt;if(low[v]>dfn[u])++ans1;
for(;;)
{
int x=stx[top],y=sty[top];--top;++cnte;
if(vis[x]!=cnt)vis[x]=cnt,++cntp;
if(vis[y]!=cnt)vis[y]=cnt,++cntp;
if(x==u&&y==v)break;
}
if(cnte>cntp)ans2+=cnte;
}
}
else if(dfn[v]<dfn[u])
{
low[u]=min(low[u],dfn[v]);
stx[++top]=u,sty[top]=v;
}
}
}
int main()
{
while(1)
{
n=read(),m=read();if(!n&&!m)break;
fill(fi+1,fi+n+1,0);tot=1;
for(int i=1;i<=m;++i)
{
int u=read(),v=read();++u,++v;
add(u,v),add(v,u);
}
fill(flag+1,flag+tot+1,0);cnt=0;
fill(dfn+1,dfn+n+1,0);sign=0;ans1=ans2=0;
fill(vis+1,vis+n+1,0);
for(int i=1;i<=n;++i)if(!dfn[i])dfs(i,i);
printf("%d %d
",ans1,ans2);
}
return 0;
}
SPOJ - STC10. Blockade, POI 2008
description:
Byteotia 城市有(n)个城镇，(m)条双向道路。每条道路连接两个不同的城镇，没有重复的道路，所有城镇连通。输出(n)个数，代表如果把与第(i)个点连接的所有边去掉，将有多少对点不能互通。
data range:
(Nle 10^5)
solution:
对于每个点，删去后至少有(2*(n-1))个点对不连通（即其他点无法到达这个已经删去的点）
对于割点，可以方便地处理出删去后每个联通块的大小（即(dfs)树上的子树大小）
然后再加上联通块两两相乘之和的贡献就是这个点的答案了
对于非割点，则没有额外的贡献
code:
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+5;
typedef long long ll;
int n,m,sign,dfn[N],low[N];
vector<int>e[N];
ll ans[N];
inline bool isnum(char &ch){return '0'<=ch&&ch<='9';}
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;!isnum(ch);ch=getchar())if(ch=='-')w=-1;
for(;isnum(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
inline ll work(vector<int>&p)
{
ll anss=0,sm=0;
for(int i=0;i<p.size();++i)
anss+=sm*p[i],sm+=1ll*p[i];
return anss;
}
int dfs(int u,int fa)
{
low[u]=dfn[u]=++sign;
int sz=1,cd=0,now=0;vector<int>p;
for(int i=0;i<e[u].size();++i)
{
int v=e[u][i];
if(v==fa)continue;
if(!dfn[v])
{
++cd;int vsz=dfs(v,u);
low[u]=min(low[u],low[v]),sz+=vsz;
if(low[v]>=dfn[u])p.pb(vsz),now+=vsz;
}
else low[u]=min(low[u],dfn[v]);
}
if(u==fa&&cd<=1)p.clear();
if(u!=fa)p.pb(n-now-1);
ans[u]+=work(p);//p中数的两两相乘之和
return sz;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;++i)
{
int u=read(),v=read();
e[u].pb(v),e[v].pb(u);
}
for(int i=1;i<=n;++i)ans[i]=1ll*(n-1);
for(int i=1;i<=n;++i)if(!dfn[i])dfs(i,i);
for(int i=1;i<=n;++i)printf("%lld
",ans[i]<<1);
return 0;
}
圆桌骑士 (Knights of the Round Table,LA3523)
description:
给出一个(N)个点的无向图，求出其中有多少个点满足它们不在任何一个长度为奇数的简单环上
data range:
(Nle 10^3)
solution:
首先对于一个奇环，它一定位于一个点双联通分量之中
于是对原图处理出所有点双
单独考虑一个点双，如果其中不存在奇环（即是一个二分图），那么其中的点都是满足条件的
否则，对于奇环上的点一定不满足，那对于奇环以外的点呢？
首先由于连通性，因此存在一条路径从v到u1
又由于双连通性，因此存在一条路径从v到u2（两条点不重复的路径分别是v->u2和v->u1->u2）
那么又由于这个环是一个奇环，所以v也一定位于一个奇环上（绿色的环或者红色的环）
然后就可做了
code:
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,sign,cnt,dfn[N],low[N],id[N],col[N];
vector<int>bcc[N],e[N];
bool G[N][N],pd[N],flag[N];
int stx[N*N],sty[N*N],top;
inline void add(int u,int t)
{
if(id[u]==t)return;
id[u]=t,bcc[t].push_back(u);
}
void dfs(int u,int fa)
{
low[u]=dfn[u]=++sign;
int cd=0;
for(int i=0;i<e[u].size();++i)
{
int v=e[u][i];
if(v==fa)continue;
if(!dfn[v])
{
++cd;stx[++top]=u,sty[top]=v;
dfs(v,u),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
++cnt;
for(;;)
{
int x=stx[top],y=sty[top];--top;
add(x,cnt),add(y,cnt);
if(x==u&&y==v)break;
}
}
}
else if(dfn[v]<dfn[u])
{
stx[++top]=u,sty[top]=v;
low[u]=min(low[u],dfn[v]);
}
}
}
bool bwpd(int u,int c)
{
if(col[u]>=0)return col[u]==c;
col[u]=c;bool o=1;
for(int i=0;i<e[u].size();++i)
{
int v=e[u][i];
if(!flag[v])continue;
o&=bwpd(v,c^1);
}
return o;
}
int main()
{
while(scanf("%d%d",&n,&m)==2&&n&&m)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j)G[i][j]=1;
while(m--)
{
int u,v;scanf("%d%d",&u,&v);
G[u][v]=G[v][u]=0;
}
for(int i=1;i<=n;++i)e[i].clear();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(G[i][j])e[i].push_back(j);
for(int i=1;i<=n;++i)bcc[i].clear();
fill(dfn+1,dfn+n+1,0);top=sign=cnt=0;
fill(id+1,id+n+1,0);fill(flag+1,flag+n+1,0);
for(int i=1;i<=n;++i)if(!dfn[i])dfs(i,i);
fill(col+1,col+n+1,-1);fill(pd+1,pd+n+1,0);
for(int i=1;i<=cnt;++i)
{
for(int j=0;j<bcc[i].size();++j)flag[bcc[i][j]]=1;
if(!bwpd(bcc[i][0],1))
for(int j=0;j<bcc[i].size();++j)pd[bcc[i][j]]=1;
for(int j=0;j<bcc[i].size();++j)flag[bcc[i][j]]=0,col[bcc[i][j]]=-1;
}
printf("%d
",count(pd+1,pd+n+1,0));
}
return 0;
}