做一次拓扑排序,入队条件为度 = 1,结束之后度仍大于1的即为在环上的点。
void top(){ while(!ts.empty()){ int k = ts.front(); ts.pop(); for(int i : G[k]){ fd[i]--; if(fd[i] == 1){ ts.push(i); } } } }
相关题目:
AtCoder Beginner Contest 266 F - Well-defined Path Queries on a Namori
链接: https://atcoder.jp/contests/abc266/tasks/abc266_f
代码:
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; vector<int> G[N]; int d[N]; int fd[N]; int cl[N]; int n; set<int> huan; queue<int> ts; void top(){ while(!ts.empty()){ int k = ts.front(); ts.pop(); for(int i : G[k]){ fd[i]--; if(fd[i] == 1){ ts.push(i); } } } } void dfs(int n, int f, int g){ for(int i : G[n]){ if(fd[i] > 1 || i == f) continue; cl[i] = g; dfs(i, n, g); } } void pre(){ for(int i = 1; i <= n; i++){ if(fd[i] == 1){ ts.push(i); fd[i]--; } } top(); for(int i = 1; i <= n; i++){ if(fd[i] > 1) { cl[i] = i; dfs(i, -1, i); } } } int main(){ cin>>n; for(int i = 1; i <= n; i++){ int u,v; scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); d[u]++, d[v]++; fd[u]++,fd[v]++; } pre(); int q; cin>>q; for(int i = 1; i <= q; i++){ int x,y; cin>>x>>y; if(cl[x] == cl[y]){ printf("Yes\n"); } else { printf("No\n"); } } }