将已知网络关键线路即桥定义为:删除此线路后,存在原网络中联通的节点,在新的网络中不连通
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int head[1000], to[100000], nxt[100000];
void addEdge(int u, int v)
{
static int tot = 1;
to[++tot] = v;
nxt[tot] = head[u];
head[u] = tot;
to[++tot] = u;
nxt[tot] = head[v];
head[v] = tot;
}
int min(int a, int b) { return a < b ? a : b; }
int dfn[1000], low[1000];
vector<pair<int, int>> br;
void tarjan(int s, int f)
{
static int index;
int cnt = 0;
dfn[s] = low[s] = ++index;
for (int p = head[s]; p; p = nxt[p])
if (!dfn[to[p]])
{
tarjan(to[p], s);
low[s] = min(low[s], low[to[p]]);
if (low[to[p]] > dfn[s])
br.push_back(s < to[p] ? make_pair(s, to[p]) : make_pair(to[p], s));
}
else if (to[p] != f)
low[s] = min(low[s], dfn[to[p]]);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m); //n节点m条连接(节点编号1-n)
for (int i = 0; i < m; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v); //编号u,v的节点连接
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i, 0);
sort(br.begin(), br.end());
for (int i = 0; i < br.size(); ++i)
printf("Bridge between Node %d and Node %d\n", br[i].first, br[i].second);
return 0;
}