Warm up
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 2012 Accepted Submission(s): 474
Problem Description
N planets are connected by M bidirectional channels that allow instant transportation. It's always possible to travel between any two planets through these channels.
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.
Input
The input contains multiple cases.
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.
Output
For each case, output the minimal number of bridges after building a new channel in a line.
思路：題目要求的是加一條邊使得剩下的橋的數量最少，我們可以先求原圖的雙連通分量，縮點後得到一棵樹，樹的每條邊都是原圖中的橋，那麼我們可以求這個樹的最長鏈，將最長鏈的兩端加一條邊後所減少的橋是最多的，所以剩下的橋顯然是最少的，所以原題目就是雙連通分量縮點並且記錄橋的個數，縮點後求樹的最長鏈，答案則是橋的數量減去最長鏈的長度。看了下大部分過這道題的都是交的C++，貌似G++不能手動擴棧，導致交G++的大部分都爆棧了。下面是代碼實現，僅供參考。。。
#pragma comment(linker, "/STACK:102400000,102400000")
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 200010
struct Edge
{
int to;
int num;
int next;
}e[2][2000100];
int box[2][maxn],cnt[2];
void init()
{
memset(box,-1,sizeof(box));
cnt[0]=cnt[1]=0;
}
void add(int from,int to,int num,int tt)
{
e[tt][cnt[tt]].to=to;
e[tt][cnt[tt]].num=num;
e[tt][cnt[tt]].next=box[tt][from];
box[tt][from]=cnt[tt]++;
}
int pre[maxn];
int low[maxn];
int bridge[1000010];
int bcnt=0;
int cnt0;
void bridge_search(int now,int edge)
{
int t;
int v,w;
low[now]=pre[now]=++cnt0;
for(t=box[0][now];t+1;t=e[0][t].next)
{
v=e[0][t].to;
if(edge!=-1&&e[0][t].num==e[0][edge].num)
continue;
if(!pre[v])
{
bridge_search(v,t);
if(low[v]<low[now])
low[now]=low[v];
if(low[v]>pre[now])
{
if(bridge[e[0][t].num]==0)
bcnt++;
bridge[e[0][t].num]=1;
}
}
else
{
if(low[now]>pre[v])
low[now]=pre[v];
}
}
}
int Bridge(int n)
{
int i;
cnt0=0;
memset(pre,0,sizeof(pre));
memset(low,0,sizeof(low));
memset(bridge,0,sizeof(bridge));
bcnt=0;
for(i=1;i<=n;i++)
{
if(!pre[i])
{
bridge_search(i,-1);
}
}
return bcnt;
}
int vis[maxn];
int dist[maxn];
void Dfs(int now,int num)
{
low[now]=num;
vis[now]=1;
int t,v,nn;
for(t=box[0][now];t+1;t=e[0][t].next)
{
v=e[0][t].to,nn=e[0][t].num;
if(bridge[nn])
continue;
if(!vis[v])
{
Dfs(v,num);
}
}
}
void lensolve(int now)
{
int t,v;
for(t=box[1][now];t+1;t=e[1][t].next)
{
v=e[1][t].to;
if(dist[v]==-1)
{
dist[v]=dist[now]+1;
lensolve(v);
}
}
}
void solve(int n,int num)
{
int i,sum=0;
memset(low,0,sizeof(low));
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
{
if(!low[i])
Dfs(i,++sum);
}
for(i=1;i<=n;i++)
{
int t,v;
for(t=box[0][i];t+1;t=e[0][t].next)
{
v=e[0][t].to;
if(low[i]!=low[v])
{
add(low[i],low[v],0,1);
add(low[v],low[i],0,1);
}
}
}
if(sum==1)
{
printf("0\n");
return;
}
memset(dist,-1,sizeof(dist));
dist[1]=0;
lensolve(1);
int ma=0,root;
for(i=1;i<=sum;i++)
{
if(ma<dist[i])
{
ma=dist[i];
root=i;
}
}
memset(dist,-1,sizeof(dist));
dist[root]=0;
lensolve(root);
ma=0;
for(i=1;i<=sum;i++)
{
if(ma<dist[i])
{
ma=dist[i];
}
}
printf("%d\n",num-ma);
}
int main()
{
// freopen("dd.txt","r",stdin);
int n,m;
while(scanf("%d%d",&n,&m)&&(n+m))
{
init();
int x,y,i;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(x!=y)
{
add(x,y,i,0);
add(y,x,i,0);
}
}
int sum=Bridge(n);
solve(n,sum);
}
return 0;
}
#pragma comment(linker, "/STACK:102400000,102400000")
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 200010
struct Edge
{
int to;
int num;
int next;
}e[2][2000100];
int box[2][maxn],cnt[2];
void init()
{
memset(box,-1,sizeof(box));
cnt[0]=cnt[1]=0;
}
void add(int from,int to,int num,int tt)
{
e[tt][cnt[tt]].to=to;
e[tt][cnt[tt]].num=num;
e[tt][cnt[tt]].next=box[tt][from];
box[tt][from]=cnt[tt]++;
}
int pre[maxn];
int low[maxn];
int bridge[1000010];
int bcnt=0;
int cnt0;
void bridge_search(int now,int edge)
{
int t;
int v,w;
low[now]=pre[now]=++cnt0;
for(t=box[0][now];t+1;t=e[0][t].next)
{
v=e[0][t].to;
if(edge!=-1&&e[0][t].num==e[0][edge].num)
continue;
if(!pre[v])
{
bridge_search(v,t);
if(low[v]<low[now])
low[now]=low[v];
if(low[v]>pre[now])
{
if(bridge[e[0][t].num]==0)
bcnt++;
bridge[e[0][t].num]=1;
}
}
else
{
if(low[now]>pre[v])
low[now]=pre[v];
}
}
}
int Bridge(int n)
{
int i;
cnt0=0;
memset(pre,0,sizeof(pre));
memset(low,0,sizeof(low));
memset(bridge,0,sizeof(bridge));
bcnt=0;
for(i=1;i<=n;i++)
{
if(!pre[i])
{
bridge_search(i,-1);
}
}
return bcnt;
}
int vis[maxn];
int dist[maxn];
void Dfs(int now,int num)
{
low[now]=num;
vis[now]=1;
int t,v,nn;
for(t=box[0][now];t+1;t=e[0][t].next)
{
v=e[0][t].to,nn=e[0][t].num;
if(bridge[nn])
continue;
if(!vis[v])
{
Dfs(v,num);
}
}
}
void lensolve(int now)
{
int t,v;
for(t=box[1][now];t+1;t=e[1][t].next)
{
v=e[1][t].to;
if(dist[v]==-1)
{
dist[v]=dist[now]+1;
lensolve(v);
}
}
}
void solve(int n,int num)
{
int i,sum=0;
memset(low,0,sizeof(low));
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
{
if(!low[i])
Dfs(i,++sum);
}
for(i=1;i<=n;i++)
{
int t,v;
for(t=box[0][i];t+1;t=e[0][t].next)
{
v=e[0][t].to;
if(low[i]!=low[v])
{
add(low[i],low[v],0,1);
add(low[v],low[i],0,1);
}
}
}
if(sum==1)
{
printf("0\n");
return;
}
memset(dist,-1,sizeof(dist));
dist[1]=0;
lensolve(1);
int ma=0,root;
for(i=1;i<=sum;i++)
{
if(ma<dist[i])
{
ma=dist[i];
root=i;
}
}
memset(dist,-1,sizeof(dist));
dist[root]=0;
lensolve(root);
ma=0;
for(i=1;i<=sum;i++)
{
if(ma<dist[i])
{
ma=dist[i];
}
}
printf("%d\n",num-ma);
}
int main()
{
// freopen("dd.txt","r",stdin);
int n,m;
while(scanf("%d%d",&n,&m)&&(n+m))
{
init();
int x,y,i;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(x!=y)
{
add(x,y,i,0);
add(y,x,i,0);
}
}
int sum=Bridge(n);
solve(n,sum);
}
return 0;
}
分享到：
