给出一个无向图G的顶点V和边E。进行Q次查询，查询从G的某个顶点V[s]到另一个顶点V[t]，是否存在2条不相交的路径。（两条路径不经过相同的边）
（注，无向图中不存在重边，也就是说确定起点和终点，他们之间最多只有1条路）
输入
第1行：2个数M N，中间用空格分开，M是顶点的数量，N是边的数量。（2 <= M <= 25000, 1 <= N <= 50000)
第2 - N + 1行，每行2个数，中间用空格分隔，分别是N条边的起点和终点的编号。例如2 4表示起点为2，终点为4，由于是无向图，所以从4到2也是可行的路径。
第N + 2行，一个数Q，表示后面将进行Q次查询。(1 <= Q <= 50000)
第N + 3 - N + 2 + Q行，每行2个数s, t，中间用空格分隔，表示查询的起点和终点。
输出
共Q行，如果从s到t存在2条不相交的路径则输出Yes，否则输出No。
输入样例
4 4
1 2
2 3
1 3
1 4
5
1 2
2 3
3 1
2 4
1 4
输出样例
Yes
Yes
Yes
No
No
仔细分析一下应该就可以看出来如果两个点之间有两条不想交的路径，那么肯定两个点在一个联通分支上，并且这两个点在环上，所以其实就是去掉桥之后的两个点是否属于一个联通分支。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int head[maxn], tot; int u[maxn], v[maxn]; int vis[maxn], low[maxn], dfn[maxn]; struct Edge { int u, v, next, id; }edge[maxn]; int n, m, Index; int col[maxn]; void init() { memset(head, -1, sizeof(head)); tot = 1; } void add(int u, int v, int id) { edge[++tot].u = u; edge[tot].v = v; edge[tot].id = id; edge[tot].next = head[u]; head[u] = tot; } void tarjan(int u, int fa) { low[u] = dfn[u] = ++Index; for (int i = head[u]; i != -1; i = edge[i].next) { int to = edge[i].v; if (to == fa) { continue; } if (!dfn[to]) { tarjan(to, u); low[u] = min(low[u], low[to]); if (low[to] > dfn[u]) { vis[edge[i].id] = 1; } } else { low[u] = min(low[u], dfn[to]); } } } void dfs(int u, int c) { col[u] = c; for (int i = head[u]; i != -1; i = edge[i].next) { int to = edge[i].v; if (!col[to]) { dfs(to, c); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); init(); cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> u[i] >> v[i]; add(u[i], v[i], i); add(v[i], u[i], i); } for (int i = 1; i <= n; i++) { if (!dfn[i]) { tarjan(i, i); } } init(); for (int i = 1; i <= m; i++) { if (!vis[i]) { add(u[i], v[i], i); add(v[i], u[i], i); } } for (int i = 1; i <= n; i++) { if (!col[i]) { dfs(i, i); } } int q, x, y; cin >> q; while (q--) { cin >> x >> y; if (col[x] != col[y]) { cout << "No" << endl; } else { cout << "Yes" << endl; } } return 0; }
