联通性.docx
《联通性.docx》由会员分享，可在线阅读，更多相关《联通性.docx（23页珍藏版）》请在冰点文库上搜索。
联通性
目录
割点2
去掉1个点，联通分量最多3
桥4
强联通6
无向图缩点树上最长路7
lca10
2-sat12
割点
constintmaxn=1008;
structE{
intv,next;
}e[maxn*maxn];
inteid,g[maxn];
voidadd（intu,intv）{
e[eid].v=v;
e[eid].next=g[u];
g[u]=eid++;
}
intdfn[maxn],low[maxn],vis[maxn],subnet[maxn];
intdfntime,son;
void_init（）{
dfntime=1,son=0;
memset（dfn,0,sizeof（dfn））;
memset（low,0,sizeof（low））;
memset（vis,0,sizeof（vis））;
memset（subnet,0,sizeof（subnet））;
memset（g,-1,sizeof（g））;
}
voiddfs（intu）{
vis[u]=1;
dfn[u]=low[u]=dfntime++;
for（inti=g[u];i!
=-1;i=e[i].next）{
intv=e[i].v;
if（!
vis[v]）{
dfs（v）;
low[u]=min（low[u],low[v]）;
if（low[v]>=dfn[u]）{
if（u==1）son++;
elsesubnet[u]++;
}
}
elselow[u]=min（low[u],dfn[v]）;
}
}
intmain（）{
intu,v,n,cas=0;
while（cin>>u&&u!
=0）{
_init（）;
cin>>v;n=max（u,v）;
add（u,v）;add（v,u）;
while（scanf（"%d",&u）&&u!
=0）{
scanf（"%d",&v）;
add（u,v）;add（v,u）;
n=max（n,u）;n=max（n,v）;
}
if（cas++）printf（"\n"）;
printf（"Network#%d\n",cas）;
dfs
（1）;
if（son>1）subnet[1]=son-1;
intf=0;
for（inti=1;i<=n;i++）{
if（subnet[i]）{
f=1;
printf（"SPFnode%dleaves%dsubnets\n",i,subnet[i]+1）;
}
}
if（!
f）puts（"NoSPFnodes"）;
}
return0;
}
去掉1个点，联通分量最多
constintmaxn=5008;
structE{
intv,next;
}e[maxn*maxn];
inteid,g[maxn];
voidadd（intu,intv）{
e[eid].v=v;
e[eid].next=g[u];
g[u]=eid++;
}
intdfn[maxn],low[maxn],vis[maxn],subnet[maxn];
intdfntime;
voiddfs（intu,intfa）{
vis[u]=1;
dfn[u]=low[u]=dfntime++;
for（inti=g[u];i!
=-1;i=e[i].next）{
intv=e[i].v;
if（v==fa）continue;
if（dfn[v]==0）{
dfs（v,fa）;
low[u]=min（low[u],low[v]）;
if（low[v]>=dfn[u]）subnet[u]++;
}
elseif（vis[v]）low[u]=min（low[u],dfn[v]）;
}
}
intmain（）{
intn,m,u,v,i,ans;
while（scanf（"%d%d",&n,&m）!
=EOF）{
memset（g,-1,sizeof（g））;
eid=0;
while（m--）{
scanf（"%d%d",&u,&v）;
add（u,v）;add（v,u）;
}
ans=0;
for（u=0;udfntime=1;
memset（vis,0,sizeof（vis））;
memset（dfn,0,sizeof（dfn））;
memset（low,0,sizeof（low））;
fill（subnet,subnet+n,1）;
intblock=0;
for（v=0;vif（v!
=u&&!
vis[v]）{
subnet[v]=0;
dfs（v,u）;
block++;
}
}
for（v=0;vif（v!
=u）ans=max（ans,block+subnet[v]-1）;
}
}
printf（"%d\n",ans）;
}
return0;
}
桥
constintmaxn=1008;
structE{
intv,w,next;
}e[maxn*maxn];
inteid,g[maxn];
voidadd（intu,intv,intw）{
e[eid].v=v;
e[eid].w=w;
e[eid].next=g[u];
g[u]=eid++;
}
intdfn[maxn],low[maxn];
intdfntime;
intgrid[maxn][maxn];
vectorbridge;
intsubnet;
void_init（）{
eid=0;
memset（g,-1,sizeof（g））;
dfntime=0;
memset（dfn,0,sizeof（dfn））;
memset（low,0,sizeof（low））;
memset（grid,0,sizeof（grid））;
bridge.clear（）;
subnet=0;
}
voiddfs（intu,intfa）{
subnet++;
dfn[u]=low[u]=++dfntime;
for（inti=g[u];i!
=-1;i=e[i].next）{
intv=e[i].v;
if（!
dfn[v]）{
dfs（v,u）;
low[u]=min（low[u],low[v]）;
if（low[v]>dfn[u]&&grid[u][v]==1）bridge.push_back（e[i].w）;
}
elseif（v!
=fa）low[u]=min（low[u],dfn[v]）;
}
}
intmain（）{
intn,m,u,v,w;
while（scanf（"%d%d",&n,&m））{
if（n==0&&m==0）break;
_init（）;
while（m--）{
scanf（"%d%d%d",&u,&v,&w）;
add（u,v,w）;
add（v,u,w）;
grid[u][v]++;
grid[v][u]++;
}
dfs（1,-1）;//for（inti=1;i<=n;i++）{if（!
dfn[i]）dfs（I,-1）;}可以求出所有的桥，即使图不连通，bridge.push_back（修改这里）
if（subnet!
=n）{
puts（"0"）;continue;
}
if（bridge.size（）==0）puts（"-1"）;
else{
sort（bridge.begin（）,bridge.end（））;
printf（"%d\n",bridge[0]==0?
1:
bridge[0]）;
}
}
return0;
}
强联通
constintmaxn=10008;
constintmaxm=50008;
structE{
intv,next;
}e[maxm];
inteid,g[maxn];
voidadd（intu,intv）{
e[eid].v=v;
e[eid].next=g[u];
g[u]=eid++;
}
//---------------
intlow[maxn],dfn[maxn],dfntime;
int_stack[maxn],top;
bool_instak[maxn];
//--------------
intbelong[maxn],bcc,bccsum[maxn];
voidtarjan（intu）{
low[u]=dfn[u]=++dfntime;
_stack[++top]=u;
_instak[u]=1;
for（inti=g[u];i!
=-1;i=e[i].next）{
intv=e[i].v;
if（!
dfn[v]）{
tarjan（v）;
low[u]=min（low[u],low[v]）;
}
elseif（_instak[v]）low[u]=min（low[u],dfn[v]）;
}
if（low[u]==dfn[u]）{
bcc++;
intv;
do{
v=_stack[top--];
_instak[v]=0;
belong[v]=bcc;
bccsum[bcc]++;
}while（v!
=u）;
}
}
voidinittarjan（）{
dfntime=0;
eid=0;
memset（g,-1,sizeof（g））;
memset（dfn,0,sizeof（dfn））;
memset（low,0,sizeof（low））;
memset（_instak,0,sizeof（_instak））;
top=0;
bcc=0;
memset（bccsum,0,sizeof（bccsum））;
}
intdg[maxn];
intmain（）{
intn,m,u,v;
while（scanf（"%d%d",&n,&m）!
=EOF）{
inittarjan（）;
while（m--）{
scanf（"%d%d",&u,&v）;
add（u,v）;
}
for（inti=1;i<=n;i++）{
if（!
dfn[i]）tarjan（i）;
}
memset（dg,0,sizeof（dg））;
for（intu=1;u<=n;u++）{
for（inti=g[u];i!
=-1;i=e[i].next）{
intv=e[i].v;
intbu=belong[u];
intbv=belong[v];
if（bu!
=bv）dg[bu]++;
}
}
int_sum=0;
for（inti=1;i<=bcc;i++）{
if（dg[i]==0）{
_sum++;
u=i;
}
}
if（_sum==1）printf（"%d\n",bccsum[u]）;
elseprintf（"0\n"）;
}
return0;
}
无向图缩点树上最长路
#pragmacomment（linker,"/STACK:
102400000,102400000"）
typedeflonglongLL;
constintmaxn=200008;
constintmaxm=2000008;
structE{
intv,next;
intvis;
}e[maxm];
inteid,g[maxn];
voidadd（intu,intv）{
e[eid].v=v;
e[eid].vis=0;
e[eid].next=g[u];
g[u]=eid++;
}
//---------------
intlow[maxn],dfn[maxn],dfntime;
int_stack[maxn],top;
bool_instak[maxn];
//--------------
intbelong[maxn],bcc,bccsum[maxn];
voidtarjan（intu）{
low[u]=dfn[u]=++dfntime;
_stack[++top]=u;
_instak[u]=1;
for（inti=g[u];i!
=-1;i=e[i].next）{
if（e[i].vis）continue;
e[i].vis=e[i^1].vis=1;
intv=e[i].v;
if（!
dfn[v]）{
tarjan（v）;
low[u]=min（low[u],low[v]）;
}
elseif（_instak[v]）low[u]=min（low[u],dfn[v]）;
}
if（low[u]==dfn[u]）{
bcc++;
intv;
do{
v=_stack[top--];
_instak[v]=0;
belong[v]=bcc;
bccsum[bcc]++;
}while（v!
=u）;
}
}
voidinittarjan（）{
dfntime=0;
eid=0;
memset（g,-1,sizeof（g））;
memset（dfn,0,sizeof（dfn））;
memset（low,0,sizeof（low））;
memset（_instak,0,sizeof（_instak））;
top=0;
bcc=0;
memset（bccsum,0,sizeof（bccsum））;
}
Ee2[maxm];
inteid2,g2[maxn];
voidadd2（intu,intv）{
e2[eid2].v=v;
e2[eid2].next=g2[u];
g2[u]=eid2++;
}
constintinf=100000000;
intdist[maxn];
intspfa（intu）{
for（inti=0;i<=bcc;i++）dist[i]=inf;
dist[u]=0;
queueq;
q.push（u）;
while（!
q.empty（））{
intu=q.front（）;q.pop（）;
for（inti=g2[u];i!
=-1;i=e2[i].next）{
intv=e2[i].v;
if（dist[v]>dist[u]+1）{
dist[v]=dist[u]+1;
q.push（v）;
}
}
}
returnmax_element（dist+1,dist+1+bcc）-dist;
}
intmain（）{
intn,m,u,v,t;
while（scanf（"%d%d",&n,&m））{
if（n==0&&m==0）break;
inittarjan（）;
while（m--）{
scanf（"%d%d",&u,&v）;
add（u,v）;
add（v,u）;
}
for（inti=1;i<=n;i++）{
if（!
dfn[i]）tarjan（i）;
}
eid2=0;
memset（g2,-1,sizeof（g2））;
for（intu=1;u<=n;u++）{
for（inti=g[u];i!
=-1;i=e[i].next）{
intv=e[i].v;
intbu=belong[u];
intbv=belong[v];
if（bu!
=bv）{
add2（bu,bv）;
}
}
}
u=spfa
（1）;
u=spfa（u）;
printf（"%d\n",bcc-dist[u]-1）;
}
return0;
}
lca
constintmaxn=10005;
constintmaxm=20005;
constintmaxq=2000005;
intn,m,q,dis[maxn],vis[maxn],father[maxn],ans[maxq/2];
structEdge{
intv,len,next;
}edge[maxm];
inttot,head[maxn];
voidadd（intu,intv,intw）{
edge[tot].v=v;
edge[tot].len=w;
edge[tot].next=head[u];
head[u]=tot++;
}
structQues{
intv,index,next;
}Q[maxq];
intq_tot,q_head[maxn];
voidadd_ques（intu,intv,intindex）{
Q[q_tot].v=v;
Q[q_tot].index=index;
Q[q_tot].next=q_head[u];
q_head[u]=q_tot++;
}
intgtf（intk）{
if（father[k]==k）returnk;
father[k]=gtf（father[k]）;
returnfather[k];
}
voidTarjan_LCA（intk,intdeep,introot）{
intj,v;
father[k]=k;
vis[k]=root;
dis[k]=deep;
for（j=head[k];j!
=-1;j=edge[j].next）{
v=edge[j].v;
if（vis[v]!
=-1）continue;
Tarjan_LCA（v,deep+edge[j].len,root）;
father[v]=k;
}
for（j=q_head[k];j!
=-1;j=Q[j].next）{
v=Q[j].v;
if（vis[v]!
=root）continue;
ans[Q[j].index]=dis[v]+dis[k]-2*dis[gtf（v）];
}
}
intmain（）{
intu,v,w;
while（scanf（"%d%d%d",&n,&m,&q）!
=-1）{
tot=q_tot=0;
memset（head,-1,sizeof（head））;
memset（q_head,-1,sizeof（q_head））;
while（m--）{
scanf（"%d%d%d",&u,&v,&w）;
add（u,v,w）;
add（v,u,w）;
}
for（inti=0;iscanf（"%d%d",&u,&v）;
ans[i]=-1;
add_ques（u,v,i）;
add_ques（v,u,i）;
}
memset（vis,-1,sizeof（vis））;
for（inti=1;i<=n;i++）{
if（vis[i]==-1）Tarjan_LCA（i,0,i）;
}
for（inti=0;iif（ans[i]==-1）printf（"Notconnected\n"）;
elseprintf（"%d\n",ans[i]）;
}
}
return0;
}
2-sat
有一个大小为N的集合={x1,x2..xn}，xi=0或1，现在给出它们之间的一些逻辑运算的结果（比如x1andx2=1），逻辑运算有ANDORXOR三种，问是否存在一种满足所有条件的取值方案。
2-sat建图题，把每个值是1（a）和0（~a）为两种状态，分清楚各种操作的本质就很简单
升级会员 