uva-796.critical links(连通图的桥)

本题大意:求出一个无向图的桥的个数并且按照顺序输出所有桥.

本题思路:注意判重就行了,就是一个桥的裸题.

　　判重思路目前知道的有两种,第一种是哈希判重,第二种和邻接矩阵的优化一样,就是只存图的上半角或者下半角.

参考代码:

 /*************************************************************************

     > File Name: uva-796.critical_links.cpp

     > Author: CruelKing

     > Mail: [email protected]

     > Created Time: 2019年09月06日 星期五 15时58分54秒

     本题思路:注意边的判重.

  ************************************************************************/

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <map>

 #include <algorithm>

 using namespace std;

 const int maxn =  + , maxm = maxn * maxn + ;

 int n;

 struct Edge {

     int to, next;

     bool cut;

 } edge[maxm];

 int head[maxn], tot;

 int low[maxn], dfn[maxn],stack[maxn];

 int Index, top, bridge;

 bool instack[maxn];

 bool cut[maxn];

 int add_block[maxn];

 void addedge(int u, int v) {

     edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cut = false;

     head[u] = tot ++;

 }

 void init() {

     memset(head, -, sizeof head);

     tot = ;

 }

 map<int, int> mp;

 vector <pair<int, int> > ans;

 void tarjan(int u, int pre) {

     int v;

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

     instack[u] = true;

     int son = ;

     int pre_cnt = ;

     for(int i = head[u]; ~i; i = edge[i].next) {

         v = edge[i].to;

         if(v == pre && pre_cnt == ) {

             pre_cnt ++;

             continue;

         }

         if(!dfn[v]) {

             son ++;

             tarjan(v, u);

             if(low[u] > low[v]) low[u] = low[v];

             if(low[v] > dfn[u]) {

                 bridge ++;

                 edge[i].cut = true;

                 edge[i ^ ].cut = true;

             }

             if(u != pre && low[v] >= dfn[u]) {

                 cut[u] = true;

                 add_block[u] ++;

             }

         } else if(low[u] > dfn[v]) low[u] = dfn[v];

     }

     if(u == pre && son > ) cut[u] = true;

     if(u == pre) add_block[u] = son - ;

     instack[u] = false;

     top --;

 }

 void solve() {

     memset(dfn, , sizeof dfn);

     memset(instack, false, sizeof instack);

     memset(add_block, , sizeof add_block);

     memset(cut, false, sizeof cut);

     Index = top = bridge = ;

     ans.clear();

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

         if(!dfn[i])

             tarjan(i, i);

     printf("%d critical links\n", bridge);

     for(int u = ; u < n; u ++) {

         for(int i = head[u]; ~i; i = edge[i].next) {

             if(edge[i].cut && edge[i].to > u) ans.push_back(make_pair(u, edge[i].to));

         }

     }

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

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

         printf("%d - %d\n", ans[i].first, ans[i].second);

     printf("\n");

 }

 inline bool ishash(int u, int v) {

     return !(mp[u * maxn + v]++ || mp[v * maxn + u]++);

 }

 int main() {

     int u, num, v;

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

         mp.clear();

         init();

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

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

             for(int i = ; i < num; i ++) {

                 scanf("%d", &v);

                 if(ishash(u, v)) continue;

                 addedge(u, v);

                 addedge(v, u);

             }

         }

         solve();

     }

     return ;

 }