0
初级守护
Tarjian割桥问题，20pts请问是哪里错了。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#define N 10010
# define forr(b, e, x) for(int i = b; i <= e; i += x)
inline int read()
{
int ans = 0;
char ch = getchar();
while (!isdigit(ch) && ch != '-') ch = getchar();
bool sign = false;
if (ch == '-') sign = true, ch = getchar();
while (ch >= '0' && ch <= '9') ans = ans * 10 + (ch - '0'), ch = getchar();
return (sign == true ? -ans : ans);
}
typedef long long ll;
using namespace std;
int mp[200][200];
int dfn[N], low[N], n, m, id, cnt, f[N];
struct edge { int t, u; }g[N];
bool cmp(edge a, edge b)
{
if (a.t != b.t) return a.u < b.u;
return a.t < b.t;
}
inline void add(int x, int y)
{
g[++ cnt].t = x;
g[cnt].u = y;
}
void tarjian(int u)
{
int c = 0, y;
dfn[u] = low[u] = ++id;
forr (1, n, 1)
{
if (!mp[u][i]) continue;
y = i;
if (dfn[y] && y != f[u]) low[u] = min(low[u], low[y]);
if (!dfn[y])
{
f[y] = u;
tarjian(y);
low[u] = min(low[u], low[y]);
if (low[y] > dfn[u]) add(u, y);
}
}
}
int main()
{
int x, y;
n = read(), m = read();
forr (1, n, 1)
{
x = read(), y = read();
mp[x][y] = mp[y][x] = 1;
}
forr (1, n, 1)
if (!dfn[i])
tarjian(i);
sort (g + 1, g + cnt + 1, cmp);
forr (1, cnt, 1)
printf("%d %d\n", min(g[i].t, g[i].u), max(g[i].t, g[i].u));
return 0;
}
1
中级守护
此题所求的是无向图中的所有割边。
对于一个联通的无向图，我们可以从一个节点开始，保证一个节点不便利两次，可以形成一棵 DFSDFS 树，定义遍历到这个节点的次序为这个节点的时间戳（用 dfndfn 表示），这样的dfn编号有一个神奇的性质：在 DFSDFS 树中，一个节点的时间戳一定小于他的子树中的所有节点。
定义 low[i]low[i] 为不经过 ii 和父节点的连边在 DFSDFS 树上可以（直接或间接）访问到的最小的时间戳，在更新的时候顺便维护 lowlow 的值。根据 dfndfn 的性质，如果 low[child]>dfn[father]low[child]>dfn[father] ，则不经过 father，childfather，child 不能访问到更小的时间戳，那么边 \langle child,father\rangle⟨child,father⟩就是割边。
0
资深守护
1
0
高级守护
1
0
初级光能
不懂
0
新手天翼
1
0
新手启示者
解题思路：
即求图中的桥（割边）
可以使用Tarjan算法
由于本题范围很小，枚举即可
枚举一条边，将这条边去掉后随便选一个点进行FloodFill，或者说从这个点开始进行DFS或BFS遍历，看是否能遍历到所有的点。
如果不可以则这条边为割边，否则不是。
