hdu 4612 边双联通 ***

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <map>
  7 #include <vector>
  8 using namespace std;
  9 
 10 const int MAXN = 200010;//点数
 11 const int MAXM = 2000010;//边数，因为是无向图，所以这个值要*2
 12 
 13 
 14 
 15 
 16 struct Edge
 17 {
 18     int to,next;
 19     bool cut;//是否是桥标记
 20     bool cong;
 21 }edge[MAXM];
 22 int head[MAXN],tot;
 23 int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~block
 24 int Index,top;
 25 int block;//边双连通块数
 26 bool Instack[MAXN];
 27 int bridge;//桥的数目
 28 
 29 void addedge(int u,int v,bool pp)
 30 {
 31     edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut=false;
 32     edge[tot].cong = pp;
 33     head[u] = tot++;
 34 }
 35 
 36 void Tarjan(int u,int pre,bool ff)
 37 {
 38     int v;
 39     Low[u] = DFN[u] = ++Index;
 40     Stack[top++] = u;
 41     Instack[u] = true;
 42     for(int i = head[u];i != -1;i = edge[i].next)
 43     {
 44         v = edge[i].to;
 45         if(v == pre && (!ff))continue;  //有重边
 46         if( !DFN[v] )
 47         {
 48             Tarjan(v,u,edge[i].cong);
 49             if( Low[u] > Low[v] )Low[u] = Low[v];
 50             if(Low[v] > DFN[u])
 51             {
 52                 bridge++;
 53                 edge[i].cut = true;
 54                 edge[i^1].cut = true;
 55             }
 56         }
 57         else if( Instack[v] && Low[u] > DFN[v] )
 58             Low[u] = DFN[v];
 59     }
 60     if(Low[u] == DFN[u])
 61     {
 62         block++;
 63         do
 64         {
 65             v = Stack[--top];
 66             Instack[v] = false;
 67             Belong[v] = block;
 68         }
 69         while( v!=u );
 70     }
 71 }
 72 void init()
 73 {
 74     tot = 0;
 75     memset(head,-1,sizeof(head));
 76 }
 77 
 78 int du[MAXN];//缩点后形成树，每个点的度数
 79 vector<int>vec[MAXN];
 80 int dep[MAXN];
 81 void dfs(int u)
 82 {
 83     for(int i = 0;i < vec[u].size();i++)
 84     {
 85         int v = vec[u][i];
 86         if(dep[v]!=-1)continue;
 87         dep[v]=dep[u]+1;
 88         dfs(v);
 89     }
 90 }
 91 void solve(int n)
 92 {
 93     memset(DFN,0,sizeof(DFN));
 94     memset(Instack,false,sizeof(Instack));
 95     Index = top = block = 0;
 96     Tarjan(1,0,false);
 97     for(int i = 1;i <= block;i++)
 98         vec[i].clear();
 99     for(int i = 1;i <= n;i++)
100        for(int j = head[i];j != -1;j = edge[j].next)
101           if(edge[j].cut)
102           {
103               vec[Belong[i]].push_back(Belong[edge[j].to]);
104           }
105     memset(dep,-1,sizeof(dep));
106     dep[1]=0;
107     dfs(1);
108     int k = 1;
109     for(int i = 1;i <= block;i++)
110         if(dep[i]>dep[k])
111           k = i;
112     memset(dep,-1,sizeof(dep));
113     dep[k]=0;
114     dfs(k);
115     int ans = 0;
116     for(int i = 1;i <= block;i++)
117         ans = max(ans,dep[i]);
118     printf("%d
",block-1-ans);
119 }
120 struct NN
121 {
122     int u,v;
123 }node[MAXM];
124 bool cmp(NN a,NN b)
125 {
126     if(a.u != b.u)return a.u<b.u;
127     else return a.v<b.v;
128 }
129 int main()
130 {
131     //freopen("in.txt","r",stdin);
132     //freopen("out.txt","w",stdout);
133     int n,m;
134     int u,v;
135     while(scanf("%d%d",&n,&m)==2)
136     {
137         if(n==0 && m==0)break;
138         init();
139         for(int i = 0;i < m;i++)
140         {
141             scanf("%d%d",&u,&v);
142             if(u==v)continue;
143             if(u>v)swap(u,v);
144             node[i].u = u;
145             node[i].v = v;
146         }
147         sort(node,node+m,cmp);
148         for(int i = 0;i < m;i++)
149         {
150             if(i == 0 || (node[i].u!=node[i-1].u || node[i].v != node[i-1].v))
151             {
152                 if(i < m-1 && (node[i].u==node[i+1].u && node[i].v == node[i+1].v))     //标记了是否出现重边
153                 {
154                     addedge(node[i].u,node[i].v,true);
155                     addedge(node[i].v,node[i].u,true);
156                 }
157                 else
158                 {
159                     addedge(node[i].u,node[i].v,false);
160                     addedge(node[i].v,node[i].u,false);
161                 }
162             }
163         }
164         solve(n);
165     }
166     return 0;
167 }