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

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

阅读量：4477 次

发布时间：2019-06-08

本文共 3017 字，大约阅读时间需要 10 分钟。

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

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

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

参考代码:

1 /*************************************************************************  2     > File Name: uva-796.critical_links.cpp  3     > Author: CruelKing  4     > Mail: 2016586625@qq.com   5     > Created Time: 2019年09月06日 星期五 15时58分54秒  6     本题思路:注意边的判重.  7  ************************************************************************/  8   9 #include 
     
       10 #include 
      
        11 #include 
       
         12 #include 
         13 #include 
         
           14 using namespace std; 15  16 const int maxn = 10000 + 5, maxm = maxn * maxn + 5; 17 int n; 18 struct Edge { 19     int to, next; 20     bool cut; 21 } edge[maxm]; 22 int head[maxn], tot; 23 int low[maxn], dfn[maxn],stack[maxn]; 24 int Index, top, bridge; 25 bool instack[maxn]; 26 bool cut[maxn]; 27 int add_block[maxn]; 28  29 void addedge(int u, int v) { 30     edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cut = false; 31     head[u] = tot ++; 32 } 33  34 void init() { 35     memset(head, -1, sizeof head); 36     tot = 0; 37 } 38  39 map
          
            mp; 40 vector 
           
            
              > ans; 41 42 void tarjan(int u, int pre) { 43 int v; 44 low[u] = dfn[u] = ++ Index; 45 instack[u] = true; 46 int son = 0; 47 int pre_cnt = 0; 48 for(int i = head[u]; ~i; i = edge[i].next) { 49 v = edge[i].to; 50 if(v == pre && pre_cnt == 0) { 51 pre_cnt ++; 52 continue; 53 } 54 if(!dfn[v]) { 55 son ++; 56 tarjan(v, u); 57 if(low[u] > low[v]) low[u] = low[v]; 58 if(low[v] > dfn[u]) { 59 bridge ++; 60 edge[i].cut = true; 61 edge[i ^ 1].cut = true; 62 } 63 if(u != pre && low[v] >= dfn[u]) { 64 cut[u] = true; 65 add_block[u] ++; 66 } 67 } else if(low[u] > dfn[v]) low[u] = dfn[v]; 68 } 69 if(u == pre && son > 1) cut[u] = true; 70 if(u == pre) add_block[u] = son - 1; 71 instack[u] = false; 72 top --; 73 } 74 75 void solve() { 76 memset(dfn, 0, sizeof dfn); 77 memset(instack, false, sizeof instack); 78 memset(add_block, 0, sizeof add_block); 79 memset(cut, false, sizeof cut); 80 Index = top = bridge = 0; 81 ans.clear(); 82 for(int i = 0; i < n; i ++) 83 if(!dfn[i]) 84 tarjan(i, i); 85 printf("%d critical links\n", bridge); 86 for(int u = 0; u < n; u ++) { 87 for(int i = head[u]; ~i; i = edge[i].next) { 88 if(edge[i].cut && edge[i].to > u) ans.push_back(make_pair(u, edge[i].to)); 89 } 90 } 91 sort(ans.begin(), ans.end()); 92 for(int i = 0; i < ans.size(); i ++) 93 printf("%d - %d\n", ans[i].first, ans[i].second); 94 printf("\n"); 95 } 96 97 inline bool ishash(int u, int v) { 98 return !(mp[u * maxn + v]++ || mp[v * maxn + u]++); 99 }100 101 int main() {102 int u, num, v;103 while(scanf("%d", &n) == 1) {104 mp.clear();105 init();106 for(int i = 0; i < n; i ++) {107 scanf("%d (%d)", &u, &num);108 for(int i = 0; i < num; i ++) {109 scanf("%d", &v);110 if(ishash(u, v)) continue;111 addedge(u, v);112 addedge(v, u);113 }114 }115 solve();116 }117 return 0;118 }