HDU 4738 Caocao's Bridge(双连通+桥)
桥
无向图中，如果去掉一条边，使得图被分成了几个部分，那么这条边就被称为桥
judge
不在环里的边都是桥
边(from, to)不在环里的标志：
low[to] > time[from]
HDU 4738 曹操的桥
无向图求桥
坑点：
- 有重边
- 初始不连通
- 无人守至少1人去
关于vector邻接表、二维邻接矩阵、链式前向星
普通vector邻接表：无需遍历+没有边权
二维邻接矩阵：遍历找边+可存边权
链式前向星：无需遍历+可存边权
普通vector邻接表+二维邻接矩阵：(利用前者)无需遍历+(利用后者)可存边权
以结构体为储存类型的vector：无需遍历+可存边权
3、5较优，1有缺陷，2耗时间，4耗空间
Code of this problem（My Code）
关于处理重边：我用嵌套的map记录重边，重边中的任意一条边均非桥！最后处理时直接跳过
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, area, bridge;
int cnt, tot, low[1005], time[1005], head[1005];
map<int, map<int, int> > mp;///重边中的任意一条均不是桥
struct edge
{
bool flag;
int from, to, w, pre;
} a[2000005];
void add(int from, int to, int w)
{
a[cnt].flag = 0;
a[cnt].from = from;
a[cnt].to = to;
a[cnt].w = w;
a[cnt].pre = head[from];
head[from] = cnt;
cnt++;
}
void Trajan(int x, int pre)
{
low[x] = time[x] = ++tot;
for(int i = head[x]; ~i; i = a[i].pre)
{
int to = a[i].to;
// if(i == (pre ^ 1))///处理重边的方法
// continue;
if(to == pre)
continue;
if(!time[to])
{
Trajan(to, x);
low[x] = min(low[x], low[to]);
if(low[to] > time[x])
{
bridge++;
a[i].flag = a[i ^ 1].flag = 1;
}
}
else
low[x] = min(low[x], time[to]);
}
}
int main()
{
while(~scanf("%d%d", &n, &m))
{
if(n == 0 && m == 0)
break;
int u, v, w;
mp.clear();
cnt = tot = area = bridge = 0;
memset(low, 0, sizeof(low));
memset(time, 0, sizeof(time));
memset(head, -1, sizeof(head));
for(int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
mp[u][v]++, mp[v][u]++;
}
for(int i = 1; i <= n; ++i)///初始可能不连通的做法
if(!time[i])
area++, Trajan(i, -1);///计算连通块
if(area > 1)
{
cout << '0' << '\n';
continue;
}
if(bridge == 0)
{
cout << "-1" << '\n';
continue;
}
int ans = 0x3f3f3f3f;
for(int i = 0; i < 2 * m; ++i)
{
u = a[i].from;
v = a[i].to;
if(mp[u][v] > 1)
continue;
if(a[i].flag && a[i].w < ans)
ans = a[i].w;
}
if(ans == 0x3f3f3f3f)
{
cout << "-1" << '\n';
continue;
}
printf("%d\n", ans == 0 ? 1 : ans);
}
return 0;
}
另一种处理重边的方法
（很简洁但我不懂）2020.4.8懂了
if(i == (pre ^ 1)) continue;Tarjan函数第二个参数，在上面我自己写的代码中，是x的父节点，在下面标准代码中，是连接x父节点与x(指向x)的那条边，
pre ^ 1是pre的反向边，我们要略过反向边，但不能略过其他的重边(同样连接了x与其父节点)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, area, bridge;
int cnt, tot, low[1005], time[1005], head[1005];
struct edge
{
bool flag;
int to, w, pre;
} a[2000005];
void add(int from, int to, int w)
{
a[cnt].flag = 0;
a[cnt].to = to;
a[cnt].w = w;
a[cnt].pre = head[from];
head[from] = cnt;
cnt++;
}
void Trajan(int x, int pre)
{
low[x] = time[x] = ++tot;
for(int i = head[x]; ~i; i = a[i].pre)
{
int to = a[i].to;
if(i == (pre ^ 1))
continue;
if(!time[to])
{
Trajan(to, i);///注意此处的i
low[x] = min(low[x], low[to]);
if(low[to] > time[x])
{
bridge++;
a[i].flag = a[i ^ 1].flag = 1;
}
}
else
low[x] = min(low[x], time[to]);
}
}
int main()
{
while(~scanf("%d%d", &n, &m))
{
if(n == 0 && m == 0)
break;
int u, v, w;
cnt = tot = area = bridge = 0;
memset(low, 0, sizeof(low));
memset(time, 0, sizeof(time));
memset(head, -1, sizeof(head));
for(int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
for(int i = 1; i <= n; ++i)
if(!time[i])
area++, Trajan(i, -1);
if(area > 1)
{
cout << '0' << '\n';
continue;
}
if(bridge == 0)
{
cout << "-1" << '\n';
continue;
}
int ans = 0x3f3f3f3f;
for(int i = 0; i < 2 * m; ++i)
if(a[i].flag && a[i].w < ans)
ans = a[i].w;
printf("%d\n", ans == 0 ? 1 : ans);
}
return 0;
}
第二份代码里的形参，第二个已不是第一个的父节点，而是父节点的head值，一条边的标号