P2860 [USACO06JAN]冗余路径Redundant Paths

题目描述

为了从F(1≤F≤5000)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．

每对草场之间已经有至少一条路径．给出所有R(F-1≤R≤10000)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量, 路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场．对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．

水一下：

这题是出去培训时老师说的送分（ming）题，然后，回来之后，改了一下午，，老师的课件十分感人，就一句话

缩边双过后把叶子两两连起来就好了

看看，这还是人话吗？

正解：

在做这题之前，要知道一个东西-----边双联通分量

若一个无向图中的去掉任意一个节点都不会改变此图的连通性，即不存在割点，则称作点双连通图。一个无向图中的每一个极大点双连通子图称作此无向图的点双连通分量。
                                                                                                                   -----度娘

举个栗子

上图中{1}，{2,3,5,6}，{4}，{7}就是边双联通分量。

由上图可得知，在边双连通分量中，任意两点都有两条互相分离的路径（例如 1-->2和1-->3--->2）

如果不在一个双连通分量中就可能经过桥，甚至不连通（例如2--->4）

由于桥必须走，所以不会有两条相互分离的路径。我们就要把一张图变成边双联通图。

以下才是正文：

首先，要找的所有的边双联通分量，所以就要找到桥，（tarjan这个东西是真的神奇，什么都能搞，虽然LCA不常用）

 1 int tarjan(int x,int edge)
 2 {
 3     dfn[x]=low[x]=++tim;
 4     for(int i=head[x];i;i=way[i].next)
 5     {
 6         int to=way[i].to;
 7         if(!dfn[to])
 8         {
 9             tarjan(to,i);
10             low[x]=min(low[x],low[to]);
11             if(dfn[x]<low[to])//桥的公式
12             {
13                 bridge[i]=bridge[i^1]=1;
14             }
15         }
16         else
17         if(i!=(edge^1))
18         {
19             low[x]=min(low[x],dfn[to]);
20         }
21     }
22 }

在一个边双连通分量中，任意两点都有至少两条互相分离的路径，所以就可以把它们缩成一个点，然后会变成一棵搜索树，就像这样

我们会发现，去掉一条边后可能会与原树不连通的，是只连有一条边的边，即叶结点（设其数量为leaf）。为令原图 边双连通（我不知道这么说对不对），我们把两个叶结点为一组用新边将其连接起来。这么看，答案似乎是

且慢！！让我们看看上图。上图

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 
  6 using namespace std;
  7 
  8 const int maxn=1e6+10;
  9 int head[maxn];
 10 int tot=1;
 11 int tim;
 12 int bridge[maxn];
 13 int to;
 14 int leave;
 15 int dfn[maxn];
 16 int n,m;
 17 int low[maxn];
 18 int color[maxn];
 19 int du[maxn];
 20 int deec;
 21 struct node
 22 {
 23     int next;
 24     int to;
 25     int from;
 26 }way[maxn];
 27 int t;
 28 int add(int x,int y)
 29 {
 30     way[++tot].next=head[x];
 31     way[tot].to=y;
 32     way[tot].from=x;
 33     head[x]=tot;
 34 }
 35 int tarjan(int x,int edge)
 36 {
 37     dfn[x]=low[x]=++tim;
 38     for(int i=head[x];i;i=way[i].next)
 39     {
 40         int to=way[i].to;
 41         if(!dfn[to])
 42         {
 43             tarjan(to,i);
 44             low[x]=min(low[x],low[to]);
 45             if(dfn[x]<low[to])
 46             {
 47                 bridge[i]=bridge[i^1]=1;
 48             }
 49         }
 50         else
 51         if(i!=(edge^1))
 52         {
 53             low[x]=min(low[x],dfn[to]);
 54         }
 55     }
 56 }
 57 int dfs(int x)
 58 {
 59     color[x]=deec;
 60     for(int i=head[x];i;i=way[i].next)
 61     {
 62         int to=way[i].to;
 63         if(color[to]!=0||bridge[i]==1)
 64         {
 65             continue;
 66         }
 67         dfs(to);
 68     }
 69 }
 70 int main()
 71 {
 72     cin>>n>>m;
 73     for(int i=1;i<=m;i++)
 74     {
 75         int x,y;
 76         cin>>x>>y;
 77         add(x,y);
 78         add(y,x);
 79     }
 80     
 81     tarjan(1,0);
 82     for(int i=1;i<=n;i++)
 83     {
 84         if(!color[i])
 85         {
 86             deec++;
 87             dfs(i);
 88             //cout<<i<<i<<i<<endl;
 89         }
 90     }//cout<<111111111<<endl;
 91     for(int i=1;i<=m;i++)
 92     {
 93         if(color[way[i*2].from]!=color[way[i*2].to])
 94         {
 95             du[color[way[i*2].from]]++;
 96             du[color[way[i*2].to]]++;
 97         }
 98     }
 99     for(int i=1;i<=deec;i++)
100     {
101         if(du[i]==1)
102         {
103             leave++;
104             //cout<<i<<endl;
105         }
106     }
107     //cout<<tim<<endl;
108     //for(int i=1;i<=10;i++)
109     //cout<<du[i]<<" ";
110     //cout<<endl<<endl;
111     cout<<(leave+1)/2<<endl;
112     return 0;
113 }