(边双联通+树直径) hdu 4612
Warm up
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 4437 Accepted Submission(s): 1001
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.
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<string> #include<algorithm> #include<queue> #include<vector> #include<set> #include<stack> using namespace std; vector<int> e[200005],mp[200005]; int n,m,use[200005],top,newflag,Dfs[200005],low[200005],isstack[200005]; int dp[200005],vis[200005],ans,bridge; stack<int> s; void init() { ans=0,bridge=0; memset(use,0,sizeof(use)); memset(Dfs,0,sizeof(Dfs)); memset(low,0,sizeof(low)); memset(isstack,0,sizeof(isstack)); top=newflag=0; while(!s.empty()) s.pop(); for(int i=1;i<=n;i++) e[i].clear(),mp[i].clear(); } int bfs(int x) { int pos; pos=x; memset(vis,0,sizeof(vis)); memset(dp,0,sizeof(dp)); queue<int> q; q.push(x); vis[x]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<mp[u].size();i++) { int v=mp[u][i]; if(vis[v]) continue; vis[v]=1; dp[v]=dp[u]+1; q.push(v); if(dp[v]>ans) { ans=dp[v]; pos=v; } } } return pos; } void tarjan(int u,int father) { Dfs[u]=low[u]=++top; s.push(u); isstack[u]=1; int cnt=0; for(int i=0;i<e[u].size();i++) { int v=e[u][i]; if(!Dfs[v]) { tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>Dfs[u]) bridge++; } else if(v==father) { if(cnt) low[u]=min(low[u],Dfs[v]); cnt++; } else if(isstack[v]) low[u]=min(low[u],Dfs[v]); } if(low[u]==Dfs[u]) { newflag++; int x; do { x=s.top(); s.pop(); isstack[x]=0; use[x]=newflag; }while(x!=u); } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; init(); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); e[x].push_back(y); e[y].push_back(x); } for(int i=1;i<=n;i++) { if(!Dfs[i]) tarjan(i,-1); } for(int i=1;i<=n;i++) { for(int j=0;j<e[i].size();j++) { int u,v; u=i,v=e[i][j]; if(use[u]!=use[v]) mp[use[u]].push_back(use[v]); } } bfs(bfs(1)); printf("%d\n",bridge-ans); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。