- 首页 > it技术 > >
/**
*求 无向图的割点和桥
*可以找出割点和桥，求删掉每个点后增加的连通块。
*需要注意重边的处理，可以先用矩阵存，再转邻接表，或者进行判重
*调用solve输出割点数，全局变量bridge记录边的个数
*/
#include
#include
#include
#include
using namespace std;
const int maxn=10010;
const int maxm=100010;
struct note
{
int v,next;
bool cut;
///是否为桥的标记
}edge[maxm];
int head[maxn],ip;
void init()
{
memset(head,-1,sizeof(head));
ip=0;
}int low[maxn],dfn[maxn],st[maxn],dex,top;
bool in_st[maxn],cut[maxn];
int add_block[maxn];
///删除一个点后增加的连通块
int bridge;
int n;
void addedge(int u,int v)
{
edge[ip].v=v,edge[ip].next=head[u],head[u]=ip++;
}void tarjan(int u,int pre)
{
low[u]=dfn[u]=++dex;
st[top++]=u;
in_st[u]=true;
int son=0;
for(int i=head[u];
i!=-1;
i=edge[i].next)
{
int v=edge[i].v;
if(v==pre)continue;
if(!dfn[v])
{
son++;
tarjan(v,u);
if(low[u]>low[v])low[u]=low[v];
///桥
///一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)dfn[u])
{
bridge++;
edge[i].cut=true;
edge[i^1].cut=true;
}
///割点
///一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。
///(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，
///即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)
if(u!=pre&&low[v]>=dfn[u])///不是树根
{
cut[u]=true;
add_block[u]++;
}
}
else if(low[u]>dfn[v])
low[u]=dfn[v];
}
///树根，需满足条件分支数大于1
if(u==pre&&son>1)cut[u]=true;
if(u==pre)add_block[u]=son-1;
in_st[u]=false;
top--;
}void solve()
{
memset(dfn,0,sizeof(dfn));
memset(in_st,false,sizeof(in_st));
memset(add_block,0,sizeof(add_block));
memset(cut,false,sizeof(cut));
dex=top=0;
bridge=0;
for(int i=1;
i<=n;
i++)
{
if(!dfn[i])
tarjan(i,i);
}
int ans=0;
for(int i=1;
i<=n;
i++)
{
if(cut[i])
ans++;
}
printf("%d\n",ans);
}
推荐阅读
