Codechef 14.2 DAGCH Dominator Tree
题目大意：
给定一张$n$个点，$m$条边的有向图，保证从1号点出发能够到达图中的所有点。随意从1号点出发开始DFS，从1开始给每一个点一个标号。给出的图中，用每个点的标号来代表原来图中的点。定义点$x$是点$y$的supreme vertex当且仅当存在一条从$x$出发到$y$的路径，使得$x$的标号小于$y$的标号，且路径上除了$x,y$两个点之外的点的标号均大于$y$的标号。定义$x$是$y$的superior vertex当且仅当$x$是$y$的所有supreme vertex中标号最小的。现在有$Q$组询问，每次给定一个标号为$P_i$的点，询问有多少个点的superior vertex是这个点。
数据范围：数据组数$\leq{10}$，$n\leq{10^5}$，$n-1\leq{m}\leq{2\times{10^5}}$，$Q\leq{10^5}$。
算法讨论：
首先需要对于给定的有向图进行标号小的点优先进行的DFS来还原搜索树。
不难发现superior vertex其实就是Domintor Tree中的semidominator，直接套用Lengauer Tarjan算法的部分就行了。
时空复杂度：
时间复杂度$O(Tm\alpha(n,m))$，空间复杂度$O(m)$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int getc() {
static const int L = 1 << 15;
static char buf[L], *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, L, stdin);
if (S == T)
return EOF;
}
return *S++;
}
int getint() {
static int x, c;
while (!isdigit(c = getc()));
x = c - '0';
while (isdigit(c = getc()))
x = (x << 1) + (x << 3) + c - '0';
return x;
}
#define N 100010
#define M 200010
vector<int> g[N], rg[N];
int sroot[N], best[N], sdom[N], id, pa[N];
int find(int x) {
if (x == sroot[x])
return x;
int y = find(sroot[x]);
if (sdom[best[x]] > sdom[best[sroot[x]]])
best[x] = best[sroot[x]];
return sroot[x] = y;
}
bool vis[N];
void dfs(int x) {
vis[x] = 1;
++id;
for (int j = 0; j < g[x].size(); ++j) {
if (!vis[g[x][j]] && g[x][j] == id + 1) {
pa[g[x][j]] = x;
dfs(g[x][j]);
}
}
}
int ans[N];
void LengauerTarjan() {
int i, j, k, v;
for (i = 1; i <= id; ++i)
sroot[i] = best[i] = sdom[i] = i;
for (i = id; i > 1; --i) {
for (j = 0; j < rg[i].size(); ++j) {
find(v = rg[i][j]);
sdom[i] = min(sdom[i], sdom[best[v]]);
}
sroot[i] = pa[i];
}
for (i = 2; i <= id; ++i)
ans[sdom[i]]++;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
int T = getint();
int n, m, q, x, i, j, k, a, b;
while (T--) {
n = getint();
m = getint();
q = getint();
id = 0;
for (i = 1; i <= n; ++i)
ans[i] = pa[i] = 0;
for (i = 1; i <= n; ++i) {
g[i].clear();
rg[i].clear();
}
for (i = 1; i <= m; ++i) {
a = getint();
b = getint();
g[a].push_back(b);
rg[b].push_back(a);
}
for (i = 1; i <= n; ++i)
sort(g[i].begin(), g[i].end());
memset(vis, 0, sizeof vis);
dfs(1);
LengauerTarjan();
for (i = 1; i <= q; ++i) {
x = getint();
if (i > 1)
putchar(' ');
printf("%d", ans[x]);
}
puts("");
}
return 0;
}
评论 (0)