指极大的不存在桥的联通分量.去掉桥会使图不连通.
tarjan算法,时间复杂度O(n+m)
1.以未建立时间戳的点为起点进行dfs,将该点压入栈中,建立该点的时间戳(f数组)并初始化从该点出发的最小的时间戳(mf数组).
2.遍历以该点为起点的所有终点,若未建立时间戳则继续进行dfs,结束后更新mf数组;否则若不为来时的边上的点,也更新mf数组.如果终点的mf值大于该点的f值,说明这条边是桥.
3.递归回到该点后,该点的mf值如果等于f值表示它是一个双连通分量的最高点,此时不断出栈至该点即可得到这个双连通分量的所有点集.
4.若要转换为树,遍历所有边,如果不在同一个双连通分量中,在这两个双连通分量之间连边.
最少加(cnt+1)/2向下取整条边把无向图中的所有点转换成双连通分量中的点,cnt为缩点后的度为1的点的个数
#include<iostream> #include<cstdio> #include<stack> #include<cstring> using namespace std; const int N=5e3+10,M=2e4+10; int h[N],nex[M],to[M],con=0,ts=0,dcc=0,id[N],deg[N],c[M]; int f[N],mf[N],in_stack[N]; void add(int a,int b) { nex[con]=h[a]; h[a]=con; to[con]=b; c[con++]=a; } stack<int>s; void dfs(int x,int from) { // cout<<x<<endl; f[x]=mf[x]=++ts; s.push(x); in_stack[x]=1; for(int i=h[x];i>=0;i=nex[i]) { int t=to[i]; if(!f[t]) { dfs(t,i); mf[x]=min(mf[x],mf[t]); // cout<<x<<' '<<f[x]<<' '<<t<<' '<<mf[t]<<endl; if(mf[t]>f[x]) {这条边是桥;} } else if(i!=(from^1)) mf[x]=min(mf[x],mf[t]); } if(f[x]==mf[x]) { int t; do { t=s.top();s.pop(); in_stack[t]=0; id[t]=dcc; }while(t!=x); dcc++; } } int main() { int f,r;cin>>f>>r; memset(h,-1,sizeof(h)); for(int i=0;i<r;++i) { int a,b;scanf("%d%d",&a,&b); add(a,b);add(b,a); } dfs(1,-1); int ans=0; for(int i=0;i<con;i+=2) { if(id[c[i]]!=id[to[i]]) { deg[id[c[i]]]++,deg[id[to[i]]]++; } } for(int i=0;i<dcc;++i) { if(deg[i]==1) ans++; } cout<<(ans+1)/2<<endl; return 0; }
