Codeforces 466E Information Graph

Information Graph

把询问离线之后就能随便搞了, 去check一下是不是祖先, 可以用倍增也能用dfs序。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std; const int N = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-; int n, m, cnt, deg[N], fa[N], op[N], x[N], y[N], depth[N], f[N][];
bool vis[N];
bool ans[N];
vector<int> G[N];
vector<int> qus[N]; int getRoot(int x) {
return x == fa[x] ? x : fa[x] = getRoot(fa[x]);
} void Merge(int x, int y) {
fa[getRoot(x)] = getRoot(y);
} void dfs(int u, int fa, int idx) {
vis[u] = idx;
depth[u] = depth[fa] + ;
f[u][] = fa;
for(int i = ; i < ; i++)
f[u][i] = f[f[u][i - ]][i - ];
for(int& v : G[u]) if(!vis[v]) dfs(v, u, idx);
} bool check(int u, int v) {
if(depth[u] < depth[v]) return false;
if(vis[u] != vis[v]) return false;
if(getRoot(u) != getRoot(v)) return false;
for(int i = ; i >= ; i--)
if(depth[f[u][i]] >= depth[v])
u = f[u][i];
return u == v;
} int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) fa[i] = i;
for(int i = ; i <= m; i++) {
scanf("%d%d", &op[i], &x[i]);
if(op[i] != ) scanf("%d", &y[i]);
if(op[i] == ) qus[y[i]].push_back(i);
if(op[i] == ) G[y[i]].push_back(x[i]), deg[x[i]]++;
}
for(int i = ; i <= n; i++)
if(!deg[i]) dfs(i, , ++cnt);
cnt = ;
for(int i = ; i <= m; i++) {
if(op[i] == ) {
Merge(x[i], y[i]);
} else if(op[i] == ) {
cnt++;
for(auto& p : qus[cnt])
if(check(x[i], x[p]))
ans[p] = true;
}
}
for(int i = ; i <= m; i++)
if(op[i] == ) printf("%s\n", ans[i] ? "YES" : "NO");
return ;
} /**/
上一篇:Codeforces 986C AND Graph dfs


下一篇:rabbitmq常用命令行汇总