HDU 4612 Warm up(边双联通求树的直径)
If we can isolate some planets from others by breaking only one channel , the channel is called a bridge of the transportation system.
People don‘t like to be isolated. So they ask what‘s the minimal number of bridges they can have if they decide to build a new channel.
Note that there could be more than one channel between two planets.
Each case starts with two positive integers N and M , indicating the number of planets and the number of channels.
(2<=N<=200000, 1<=M<=1000000)
Next M lines each contains two positive integers A and B, indicating a channel between planet A and B in the system. Planets are numbered by 1..N.
A line with two integers ‘0‘ terminates the input.
4 4 1 2 1 3 1 4 2 3 0 0
0
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<string> #include<iostream> #include<queue> #include<cmath> #include<map> #include<stack> #include<bitset> using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) typedef long long LL; typedef pair<int,int>pil; const int maxn=200000+100; const int maxm=3000000+100; struct node{ int to,next; bool col;//为桥 }e[maxm],e1[maxm]; int head[maxn],cnt,cntE,cnte; int DFN[maxn],low[maxn]; int s[maxn],instack[maxn]; int idex,top,bridge; int belong[maxn],h[maxn]; int d[maxn],vis[maxn];//为割;删除点后增加的联通快 int n,m; void init() { cnt=top=idex=0; cnte=bridge=cntE=0; CLEAR(head,-1); CLEAR(DFN,0); CLEAR(low,0); CLEAR(instack,0); CLEAR(belong,0); CLEAR(h,-1); CLEAR(vis,0); CLEAR(d,0); } void addedge(int u,int v) { e[cntE].to=v;e[cntE].next=head[u]; e[cntE].col=false;head[u]=cntE++; } void addedge1(int u,int v) { e1[cnte].to=v;e1[cnte].next=h[u]; h[u]=cnte++; } void Tarjan(int u,int pre) { int v; low[u]=DFN[u]=++idex; s[top++]=u; instack[u]=1; int pre_num=0; for(int i=head[u];i!=-1;i=e[i].next) { v=e[i].to; if(v==pre&&!pre_num) { pre_num++; continue; } if(!DFN[v]) { Tarjan(v,u); if(low[u]>low[v]) low[u]=low[v]; if(low[v]>DFN[u])//桥 { bridge++; e[i].col=true; e[i^1].col=true; } } else if(instack[v]&&low[u]>DFN[v]) low[u]=DFN[v]; } if(low[u]==DFN[u]) { cnt++; do{ v=s[--top]; instack[v]=0; belong[v]=cnt; }while(v!=u); } } void dfs(int u,int depth) { d[u]=depth; vis[u]=1; for(int i=h[u];i!=-1;i=e1[i].next) { int v=e1[i].to; if(!vis[v]) dfs(v,depth+1); } } void work() { REPF(i,1,n) if(!DFN[i]) Tarjan(i,-1); REPF(u,1,n) for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(belong[u]!=belong[v]) { addedge1(belong[u],belong[v]); addedge1(belong[v],belong[u]); } } dfs(1,0); int pos=1; for(int i=1;i<=cnt;i++) if(d[i]>d[pos]) pos=i; CLEAR(vis,0); CLEAR(d,0); dfs(pos,0); int ans=0; REPF(i,1,cnt) ans=max(ans,d[i]); printf("%d\n",bridge-ans); } int main() { int u,v; while(~scanf("%d%d",&n,&m)&&(n+m)) { init(); REPF(i,1,m) { scanf("%d%d",&u,&v); if(u==v) continue; addedge(u,v); addedge(v,u); } work(); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。