题目链接:https://atcoder.jp/contests/abc318/tasks/abc318_g
题目大意:
给出一个有 \(n\) 个顶点和 \(m\) 条边的无向连通图 \(G\),没有重边和自环。
顶点的编号为 \(1 \sim n\),边的编号为 \(1 \sim m\),第 \(i\) 条边连接顶点 \(u_i\) 和 \(v_i\)。
给出图上三个不同的顶点 \(A,B,C\)。判断是否有从点 \(A\) 经过点 \(B\) 到点 \(C\) 的简单路径。
简单路径指路径上的点互不相同,即不重复经过同一个点。
解题思路:
建立圆方树。则在 \(A\) 点到 \(C\) 点的路径中存在点 \(B\) 或者存在与点 \(B\) 邻接的方点,答案为 Yes
;否则为 No
。
示例程序:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5;
int n, m, A, B, C, dfn[maxn], low[maxn], idx, tot, fa[maxn];
stack<int> stk;
vector<int> g[maxn], G[maxn];
bool vis[maxn];
void tarjan(int u) {
dfn[u] = low[u] = ++idx;
stk.push(u);
for (auto v : g[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
if (low[v] == dfn[u]) {
fa[++tot] = u;
G[u].push_back(tot);
int x;
do {
x = stk.top();
stk.pop();
fa[x] = tot;
G[tot].push_back(x);
} while (x != v);
}
}
else
low[u] = min(low[u], dfn[v]);
}
}
int main() {
scanf("%d%d%d%d%d", &n, &m, &A, &B, &C);
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
tot = n;
tarjan(A);
bool flag = false;
for (int u = C; u && !flag; u = fa[u]) {
if (u == B) flag = true;
if (u > n) {
for (auto v : G[u])
if (v == B)
flag = true;
}
}
puts(flag ? "Yes" : "No");
return 0;
}
标签:abc318,int,题解,d%,tot,圆方树,maxn,low,dfn
From: https://www.cnblogs.com/quanjun/p/18521097