HDU 3394 Railway —— （点双联通，记录块信息）

　　这题是比较模板的找点双联通并记录的题目。

　　题意大概是：一个公园有n个景点，1.所有游客都是绕环旅游的，找出所有不在环内的路的条数；2.如果两个环中有重复的边，那么这些边是冲突的，问冲突的边的总数。

　　分析：1.即桥的条数；2.找出点双联通分量，在他们内部找重复的边，或者换句话说，找出所有点双联通分量，边数大于点数的，这些边都是冲突的。

　　那么，什么是点双联通分量呢，就是任意两点都有两条或以上的路径，这些路径的点除了这两点以外，都不相同，或者说，内部无割点，像数字8的形状就不是，8是边双联通；或者再换句话说，任意两边都在一个简单环内。

　　而边双联通图呢，是任意一边都在一个简单环内。或者说，所有边都不是桥。

　　搞清楚这两点就可以了。然后代码都是模板的问题，代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <stack>

 #include <set>

 using namespace std;

 typedef pair<int,int> pii;

 int n,m;

 vector<int> G[+];

 int dfn[+],low[+];

 int dfs_clock,cnt_qiao,cnt_scc;

 vector<pii> block[+];

 int vis[+];

 stack<pii> S;

 void init()

 {

     for(int i=;i<n;i++) G[i].clear();

     memset(dfn,,sizeof(dfn));

     dfs_clock=;

     cnt_qiao=;

     cnt_scc=;

     for(int i=;i<n;i++) block[i].clear();

 }

 void dfs(int u,int fa)

 {

     dfn[u]=low[u]=++dfs_clock;

     for(int i=;i<G[u].size();i++)

     {

         int v = G[u][i];

         if(v==fa) continue;

         //S.push(pii(u,v));

         //不能在这里push边，不然会出现重边

         if(!dfn[v])   //这是从父到子的访问顺序，只有这个顺序才能判断是不是割点或者桥

         {

             S.push(pii(u,v));

             dfs(v,u);

             low[u]=min(low[u],low[v]);

             if(dfn[u]<=low[v]) //这一点是准割点（在根处不成立）

             {

                 for(;;)

                 {

                     pii t = S.top();S.pop();

                     block[cnt_scc].push_back(t);

                     if(t.first==u && t.second==v) break;

                 }

                 cnt_scc++;

             }

             if(dfn[u]<low[v]) cnt_qiao++;

         }

         else if(dfn[v]<dfn[u])    //这是子到父的访问顺序，即反向边

         {

             S.push(pii(u,v));

             low[u]=min(low[u],dfn[v]);

         }

     }

 }

 void solve()

 {

     for(int i=;i<n;i++) if(!dfn[i]) dfs(i,-);

     int cnt=;

     for(int i=;i<cnt_scc;i++)

     {

         memset(vis,,sizeof(vis));

         int cnt_edge = block[i].size();

         int cnt_point=;

         for(int j=;j<block[i].size();j++)

         {

             pii t = block[i][j];

             int u = t.first,v = t.second;

             if(!vis[u]) vis[u]=,cnt_point++;

             if(!vis[v]) vis[v]=,cnt_point++;

         }

         if(cnt_point<cnt_edge)

         {

             cnt+=cnt_edge;

         }

     }

     printf("%d %d\n",cnt_qiao,cnt);

 }

 int main()

 {

     while(scanf("%d%d",&n,&m)==)

     {

         if(n== && m==) break;

         init();

         for(int i=;i<=m;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             G[u].push_back(v);

             G[v].push_back(u);

         }

         solve();

     }

     return ;

 }