【求无向图的桥，有重边】ZOJ - 2588 Burning Bridges

模板题——求割点与桥

题意，要使一个无向图不连通，输出必定要删掉的边的数量及其编号。求桥的裸题，可拿来练手。

套模板的时候注意本题两节点之间可能有多条边，而模板是不判重边的，所以直接套模板的话，会将重边也当做桥输出，因此要在判断桥的时候加一个判断，即当且仅当两点之间仅有一条边，且满足dfn[cur] < low[i]，(cur, i)才是桥。

另外本题节点数为10，用邻接矩阵的话会内存超限，所以我用了了一个multiset存储边及其编号。

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<vector>

 #include<set>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 const int MAX_V = ;

 const int MAX_E = ;

 struct Edge

 {

     int to, id;

     Edge() {}

     Edge(int _t, int _i):to(_t), id(_i) {}

     bool operator < (const Edge& rhs) const

     {

         return to < rhs.to;

     }

 };

 multiset<Edge> edge[MAX_V];

 multiset<int> tms[MAX_V];

 vector<int> ans;

 int vis[MAX_V]; //结点v当前访问状态，0表示未访问，1表示在栈中，2表示已经访问过

 int dfn[MAX_V]; //结点v被访问时的深度

 int low[MAX_V]; //结点v可以到达的访问时间最早的祖先的深度

 void cut_bridge(int cur, int father, int dep, int n) //vertex: 0~n-1

 {

     vis[cur] = ;

     dfn[cur] = dep;

     low[cur] = dep;

     int children = ;

     int sz = edge[cur].size();

     for(multiset<Edge>::iterator it = edge[cur].begin(); it != edge[cur].end(); it++)

     {

         int id = (*it).id;

         int i = (*it).to;

         if(i != father && vis[i] == ) //i在当前栈中，说明图中有一个环，用i的深度更新cur的low值；

         {

             if(dfn[i] < low[cur]) low[cur] = dfn[i]; //将结点cur可以到达的访问时间最早的祖先的深度更新为结点i被访问时的深度；

         }

         if(vis[i] == ) //i没被访问过，递归访问节点i，并用i的可以到达的最早祖先来更新cur的low值；

         {

             cut_bridge(i, cur, dep+, n);

             if(low[i] < low[cur]) low[cur] = low[i];

             if(low[i] > dfn[cur] && tms[cur].count(i) == )

             {

                 ans.push_back(id);

             }//判断桥

         }

     }

     vis[cur] = ;

 }

 void init(int n)

 {

     ans.clear();

     memset(vis, , sizeof(vis));

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

     {

         edge[i].clear();

         tms[i].clear();

     }

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     for(int kase = ; kase < T; kase++)

     {

         if(kase) printf("\n");

         int n, m;

         scanf("%d%d", &n, &m);

         init(n);

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

         {

             int u, v;

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

             Edge e1(v, i+), e2(u, i+);

             edge[u].insert(e1);

             edge[v].insert(e2);

             tms[u].insert(v);

             tms[v].insert(u);

         }

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

             if(vis[i] == )

                 cut_bridge(i, -, , n);

         sort(ans.begin(), ans.end());

         printf("%d\n", ans.size());

         for(int i = ; i < ans.size(); i++)

         {

             if(i) printf(" ");

             printf("%d", ans[i]);

         }

         if(ans.size()) printf("\n");

     }

     return ;

 }

ZOJ 2588