强连通专题
求割点（无向边）：
所谓的割点，就是删除某个点，图便不连通了。
POJ 1523
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=1111;
struct Edge
{
int to,next;
}edge[MN<<2];
int dfn[MN];
int low[MN];
int head[MN<<2];
int subnet[MN];
int E,tp,root;
int vis[MN];
void Init()
{
memset(dfn,-1,sizeof(dfn));
memset(low,0,sizeof(low));
memset(head,-1,sizeof(head));
memset(subnet,0,sizeof(subnet));
memset(vis,0,sizeof(vis));
E=tp=0;
}
void Add(int a,int b)
{
edge[E].to=b;
edge[E].next=head[a];
head[a]=E++;
}
void tarjan(int u,int fa)
{
int son=0;
vis[u]=1;
dfn[u]=low[u]=++tp;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(vis[v]==1 && v!=fa)
low[u]=min(low[u],dfn[v]);
if(!vis[v])
{
tarjan(v,u);
son++;
low[u]=min(low[u],low[v]);
if((u==root && son>1) || (u!=root)&& dfn[u]<=low[v])
subnet[u]++;
}
}
vis[u]=2;
}
int main()
{
int i,cas=1,n,a,b,nodes;
while(scanf("%d",&n) && n)
{
nodes=n;
Init();
scanf("%d",&b);
Add(n,b);
Add(b,n);
while(scanf("%d",&a) && a)
{
scanf("%d",&b);
if(nodes<a) nodes=a;
if(nodes<b) nodes=b;
Add(a,b);
Add(b,a);
}
for(i=1;i<=nodes;i++)
{
if(dfn[i]==-1)
{
root=i;
tarjan(i,-1);
}
}
int flag=0;
printf("Network #%d\n",cas++);
for(i=1;i<=nodes;i++)
{
if(subnet[i]>=1)
{
flag=1;
printf(" SPF node %d leaves %d subnets\n",i,subnet[i]+1);
}
}
if(flag==0) printf(" No SPF nodes\n");
puts("");
}
}求割边
HDU 4738（无向边）
http://acm.hdu.edu.cn/showproblem.php?pid=4738
题意：判断一个图是否联通，并给出每条边的权值，若联通则让你找出最小权值的割边。
注意：当所有边的权值为0的话且联通的话输出1,若不联通的话输出0
由于存储权值的数组开小了，所以超时。。。。超时。。。。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=1010;
int dfn[MN],low[MN],num[MN];
int vis[MN],ww[MN*MN];
int tp,E;
int ans,cnt;
struct Edge
{
int next,to;
int tag;//判断是否有重边
int pos;//第几条边
int w;
} edge[MN*MN];
int head[MN*MN];
int bridge[MN*MN];
void init()
{
memset(dfn,-1,sizeof(dfn));
memset(low,0,sizeof(low));
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
E=tp=0;
}
int Add(int a,int b,int pos,int c)
{
for(int i=head[a]; i!=-1; i=edge[i].next)
{
if(edge[i].to==b)
{
edge[i].tag++;
return true;
}
}
edge[E].tag=0;
edge[E].w=c;
edge[E].pos=c;
edge[E].to=b;
edge[E].next=head[a];
head[a]=E++;
}
void tarjan(int u,int fa)
{
dfn[u]=low[u]=++tp;
vis[u]=1;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
if(!vis[v])
{
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u] && !edge[i].tag)
{
ww[++ans]=edge[i].w;
}
}
else
low[u]=min(low[u],dfn[v]);
}
}
int main()
{
int T,n,m,a,b,c;
while(scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
init();
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&a,&b,&c);
Add(a,b,i,c);
Add(b,a,i,c);
}
ans=0;
tarjan(1,-1);
cnt=0;
for(int j=1; j<=n; j++)
{
if(!vis[j]) cnt++;
}
if(cnt) printf("0\n");
else
{
if(ans)
{
int MIN=99999999;
for(int i=1; i<=ans; i++)
{
if(MIN>ww[i]) MIN=ww[i];
}
if(MIN==0) printf("1\n");
else printf("%d\n",MIN);
}
else printf("-1\n");
}
}
return 0;
}POJ 3177（无向图求）
题意：农场主有F片田野，他想把牛迁移，但是牛要是只走一条路的话会把这条路的草都吃没了，所以他想
从a到b之间有大于等于2的路。现在给你一个联通的图，问最少加多少条边能够让任意两点有大于等于2
条路可以走、
分析：求边双联通分量
求双联通分量然后缩点，再求缩点后的叶子几点，加的边就是（ans+1）/2;
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=5010;
const int MM= 10011;
int low[MN],dfn[MN];
int instack[MM];
int subnet[MN],vis[MN];
int stap[MN],head[MM];
int degree[MN];
int belong[MN];
int tp,root;
int E,p;
int ans;
int cnt;
struct Edge
{
int to,next;
} edge[MM];
void Addedge(int a,int b)
{
for(int i=head[a]; i!=-1; i=edge[i].next)
{
if(edge[i].to==b)
{
return ;
}
}
edge[E].to=b;
edge[E].next=head[a];
head[a]=E++;
}
void Init()
{
memset(dfn,-1,sizeof(dfn));
memset(low,0,sizeof(low));
memset(head,-1,sizeof(head));
memset(degree,0,sizeof(degree));
memset(instack,0,sizeof(instack));
memset(belong,-1,sizeof(belong));
tp=E=p=0;
ans=cnt=0;
}
void tarjan(int x,int fa)
{
low[x]=dfn[x]=++tp;
stap[++p]=x;
instack[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
if(dfn[v]==-1)
{
tarjan(v,x);
if(low[x]>low[v])
low[x]=low[v];
}
else if(instack[v] && dfn[v]<low[x])
low[x]=dfn[v];
}
if(low[x]==dfn[x])
{
int top;
do
{
top=stap[p];
instack[top]=0;
belong[top]=cnt;
p--;
}
while(x!=top);
cnt++;
}
}
int main()
{
char s[100];
int i,j,n,m,a,b;
int cas=1;
while(scanf("%d%d",&n,&m)!=EOF)
{
Init();
for(i=1; i<=m; i++)
{
scanf("%d%d",&a,&b);
Addedge(a,b);
Addedge(b,a);
}
for(i=1; i<=n; i++)
{
if(dfn[i]==-1)
{
tarjan(i,-1);
}
}
for(i=1;i<=n;i++)
{
for(j=head[i];j!=-1;j=edge[j].next)
{
int x=belong[i];
int y=belong[edge[j].to];
if(x!=y)//当x和y不属于同一个缩点的时候
{
degree[x]++;
degree[y]++;
}
}
}
int res=0;
for(i=0;i<cnt;i++)//由于无向图每个点的度加了两次
{//当度是1的时候表明是叶子节点
if(degree[i]/2==1) res++;
}
// printf("Output for Sample Input %d\n",cas++);
printf("%d\n\n",(res+1)/2);
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013-10-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读