題目鏈接 ：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=122091#problem/C

題目：

In a computer network a link L, which interconnects two servers, is considered critical if there are at
least two servers A and B such that all network interconnection paths between A and B pass through L.
Removing a critical link generates two disjoint sub–networks such that any two servers of a sub–network
are interconnected. For example, the network shown in ?gure 1 has three critical links that are marked
bold: 0 -1, 3 - 4 and 6 - 7.
Figure 1: Critical links
It is known that:
1. the connection links are bi–directional;
2. a server is not directly connected to itself;
3. two servers are interconnected if they are directly connected or if they are interconnected with
the same server;
4. the network can have stand–alone sub–networks.
Write a program that ?nds all critical links of a given computer network.
Input
The program reads sets of data from a text ?le. Each data set speci?es the structure of a network and
has the format:
no of servers
server0 (no of direct connections) connected server . . . connected server
. . .
serverno of servers (no of direct connections) connected server . . . connected server
The ?rst line contains a positive integer no of servers(possibly 0) which is the number of network
servers. The next no of servers lines, one for each server in the network, are randomly ordered and
show the way servers are connected. The line corresponding to serverk, 0 ≤ k ≤ no of servers ? 1,
speci?es the number of direct connections of serverk and the servers which are directly connected to
serverk. Servers are represented by integers from 0 to no of servers ? 1. Input data are correct. The
?rst data set from sample input below corresponds to the network in ?gure 1, while the second data
set speci?es an empty network.
Output
The result of the program is on standard output. For each data set the program prints the number of
critical links and the critical links, one link per line, starting from the beginning of the line, as shown
in the sample output below. The links are listed in ascending order according to their ?rst element.
The output for the data set is followed by an empty line.
Sample Input
8
0 (1) 1
1 (3) 2 0 3
2 (2) 1 3
3 (3) 1 2 4
4 (1) 3
7 (1) 6
6 (1) 7
5 (0)
0
Sample Output
3 critical links
0 - 1
3 - 4
6 - 7
0 critical links

題意： 在電腦網絡中，有的網絡是兩個服務器彼此互聯的。現給你網絡服務器互聯的圖，問你主要的線路有幾條。（主要線路指若斷了這條線路，那么整個局域網則不能連接在一塊，也就是橋）

vector 代碼

#include <iostream> #include <cstdlib> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <stack> #include <cstring> using namespace std; #define INF 0xfffffff #define maxn 11005vector< vector <int> >G; int dfn[maxn], low[maxn], father[maxn]; int n, times, cnt;struct node {int x, y; }brige[maxn];bool cmp(node a, node b) {if(a.x != b.x)return a.x<b.x;return a.y<b.y; } void Init() {G.clear();G.resize(n+5);memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(father, 0, sizeof(father));times = 1; }void Tarjan(int u, int fa) {dfn[u] = low[u] = times++;father[u] = fa;int len = G[u].size(), v;for(int i=0; i<len; i++){v = G[u][i];if(!dfn[v]){Tarjan(v, u);low[u] = min(low[u], low[v]);}else if(fa != v)low[u] = min(low[u], dfn[v]);} }void solve() {int v;cnt = 0;for(int i=0; i<n; i++){if(!low[i])Tarjan(i, -1);}for(int i=0; i<n; i++){v = father[i];if(v!=-1 && dfn[v] < low[i]){brige[cnt].x = i;brige[cnt].y = v;if(brige[cnt].x > brige[cnt].y)swap(brige[cnt].x, brige[cnt].y);cnt++;}}sort(brige, brige+cnt, cmp);printf("%d critical links\n", cnt);for(int i=0; i<cnt; i++){printf("%d - %d\n", brige[i].x, brige[i].y);}printf("\n"); } int main() {while(scanf("%d",&n) != EOF){Init();for(int i=0; i<n; i++){int a, b, m;scanf("%d (%d)",&a,&m);while(m--){scanf("%d", &b);G[a].push_back(b);G[b].push_back(a);}}solve();}return 0; } View Code

?

鄰接表代碼

#include <iostream> #include <cstdlib> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <stack> #include <cstring> using namespace std; #define INF 0xfffffff #define maxn 1005 int head[maxn], low[maxn], dfn[maxn], father[maxn]; int cnt, times, n;struct node {int v, next; }maps[maxn*maxn];struct Brige {int x,y; }brige[maxn];bool cmp(Brige a, Brige b) {if(a.x != b.x)return a.x<b.x;return a.y<b.y; }void Add(int u, int v) {maps[cnt].v = v;maps[cnt].next = head[u];head[u] = cnt ++; }void Init() {memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(father, 0, sizeof(father));memset(maps, 0, sizeof(maps));memset(head, -1, sizeof(head));times = 1; }void Tarjan(int u, int fa) {dfn[u] = low[u] = times++;father[u] = fa;int v;for(int i=head[u]; i!=-1; i=maps[i].next){v = maps[i].v;if(!dfn[v]){Tarjan(v, u);low[u] = min(low[u], low[v]);}else if(fa != v)low[u] = min(low[u], dfn[v]);} }void solve() {int v;cnt = 0;for(int i=0; i<n; i++){if(!low[i])Tarjan(i, -1);}for(int i=0; i<n; i++){v = father[i];if(v!=-1 && dfn[v] < low[i]){brige[cnt].x = i;brige[cnt].y = v;if(brige[cnt].x > brige[cnt].y)swap(brige[cnt].x, brige[cnt].y);cnt++;}}sort(brige, brige+cnt, cmp);printf("%d critical links\n", cnt);for(int i=0; i<cnt; i++){printf("%d - %d\n", brige[i].x, brige[i].y);}printf("\n"); } int main() {while(scanf("%d",&n) != EOF){Init();cnt = 0;for(int i=0; i<n; i++){int a, b, m;scanf("%d (%d)",&a,&m);while(m--){scanf("%d", &b);Add(a, b);Add(b, a);}}solve();}return 0; } View Code

?

轉載于:https://www.cnblogs.com/daydayupacm/p/5672878.html

總結

以上是生活随笔為你收集整理的无向图求桥 UVA 796的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。