CRB and Graph

CRB and Graph

Description

一个连通，n 个顶点和 m 条边的无向图被给了 CRB。

一对顶点 ( u , v ) (u,v) (u,v)（u 认证机构的任务是寻找每条边的关键对。帮助他！）

Input

有多个测试案例。输入的第一行包含一个整数 t，表示测试用例的数目。

对于每一个测试案例：

第一行包含两个整数 n，m 表示顶点数和边数。

接下来的 m 行包含一个整数对 a 和 b，表示 a 和 b 之间一个无向边。

1 ≤ t ≤ 12 1≤t≤12 1≤t≤12

1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^ 5 1≤n,m≤105

1 ≤ a , b ≤ n 1≤a,b≤n 1≤a,b≤n

所有给定的图连接。

没有重边和自循环，图是简单的。

Output

对于每一条边， 若删除该边后存在两点不可达，则输出这两个点， 如果存在多个则输出u尽可能大，如果还存在多个则v尽可能小的。 不存在输出0 0。

Sample Input

2
3 2
3 1
2 3
3 3
1 2
2 3
3 1

Sample Output

1 2
2 3
0 0
0 0
0 0

题目分析

去掉一条边，问去掉之后不能互通的两个点的编号（u 尽量大，v 尽量小）。

我们先用 Tarjan 找割边。

首先很明显，一条非割边的边在去掉之后，不会对其他点产生影响，所以输出0 0 。

但若该边是割边，去掉之后会将图分成两个连通块，我们要的答案就分别在这两个连通块中。

首先，n 所在的连通块中是我们要的点 v。

因为 n 不能为点 u，否则 v 就不再是合法节点了。

其次，为了满足题目对答案的要求，易得 v ← u + 1 v gets u+1 v←u+1。

综上我们只需要求出 n 不在的连通块的最大节点，就可以输出答案了。

这时候我们用 dfs 从 n 去遍历每一个节点，记录它的子节点最大编号以及它的深度。

最后遍历每一条输入过的边，如果 d e p u i > d e p v i dep_{u_i} > dep_{v_i} depui​​>depvi​​，就证明 v a l u i ≤ v a l v i val_{u_i} ≤ val_{v_i} valui​​≤valvi​​（val 存一个节点的最大儿子编号），那就输出 v a l u i val_{u_i} valui​​， 然后再输出 v a l u i + 1 val_{u_i}+1 valui​​+1。

反之道理一样。

代码实现

在双向边建边的部分这道题要提一下。

因为我们要在输出结果的时候使用开始从 1 循环到 m 输入的边的两个顶点，

所以，我们 vis 数组对边的编号的存储要和输入的一样，还要满足都能从两个有向边编号指向这个边。

这时我们就需要在赋值判桥数组的时候对编号进行改变。

我们 v i s i + 1 > > 1 ← 1 vis_{i+1>>1} gets 1 visi+1>>1​←1，这样我们就可以从 1 到 m 访问边了。

#include<bits/stdc++.h>
using namespace std;//边双const int maxn = 1000005;
int n, m;
int cnt, hd[maxn];
struct node{int to, nxt;
}e[maxn * 2];
int low[maxn], dfn[maxn]; 
int co[maxn], reco[maxn], recoa[maxn];
int st[maxn], vis[maxn];
int tmp, col, top;
int root;
int u[maxn], v[maxn];
int dep[maxn], val[maxn];void init ()
{cnt = tmp = col = top = 0;memset (hd, 0, sizeof hd);memset (e, 0, sizeof e);memset (dfn, 0, sizeof dfn);memset (low, 0, sizeof low);memset (vis, 0, sizeof vis);memset (co, 0, sizeof co);memset (reco, 0x7f, sizeof reco);memset (recoa, 0, sizeof recoa);memset (u, 0, sizeof u);memset (v, 0, sizeof v);memset (dep, 0, sizeof dep);memset (val, 0, sizeof val);
}int read ()
{int x = 1, s = 0;char ch = getchar ();while (ch < '0' or ch > '9') {if (ch == '-') x = -1; ch = getchar ();}while (ch >= '0' and ch <= '9') {s = s * 10 + ch - '0'; ch = getchar ();}return x * s;
}void add (int u, int v)
{e[++cnt].to = v;e[cnt].nxt = hd[u];hd[u] = cnt;
}int find (int x)
{if (x % 2 == 0) return x - 1;return x + 1;
}void tarjan (int u, int fa)
{dfn[u] = low[u] = ++tmp;for (int i = hd[u]; i; i = e[i].nxt){int v = e[i].to;if (v == fa) continue;	if (!dfn[v]){tarjan (v, u);low[u] = min (low[u], low[v]);if (dfn[u] < low[v]){vis[i + 1 >> 1] = 1;}}else low[u] = min (low[u], dfn[v]);}}void dfs (int u, int d)
{dep[u] = d;for (int i = hd[u]; i; i = e[i].nxt){int v = e[i].to;if (dep[v]) continue;dfs (v, d + 1);val[u] = max (val[u], val[v]);}
}int main ()
{int T;T = read ();while (T--){init ();
//		memset (reco, 0x7f, sizeof reco);n = read (), m = read ();for (int i = 1; i <= m; i++){u[i] = read (), v[i] = read ();add (u[i], v[i]), add (v[i], u[i]);}for (int i = 1; i <= n; i++) val[i] = i;dfs (n, 1);for (int i = 1; i <= n; i++){if (!dfn[i]){root = i;tarjan (i, -1);}}for (int i = 1; i <= m; i++){if (!vis[i]) {printf ("0 0n");continue;}
//			printf ("%d %dn", reco[co[u[i]]], recoa[co[v[i]]]);if (dep[u[i]] > dep[v[i]]) printf ("%d %dn", val[u[i]], val[u[i]] + 1);else printf ("%d %dn", val[v[i]], val[v[i]] + 1);}}return 0;
}

—— E n d End End——