Codechef 15.5 GRAPHCNT Dominator Tree
题目大意：
给定一张$n$个点，$m$条边的有向图，问存在多少对点$(X,Y)$，使得存在两条从点1出发分别到$X$和$Y$的路径满足这两条路径只在点1处相交。
数据范围$1\leq{n}\leq{10^5},0\leq{m}\leq{5\times{10^5}}$。
算法讨论：
我们求出这张无向图以$1$为根的Dominator Tree，则点对$(X,Y)$合法当且仅当$X,Y$在Dominator Tree上的LCA为点1。
于是我们直接求出Dominator Tree，然后在树上进行简单的统计即可。
关于Dominator Tree的更多内容请参见李煜东的《图连通性若干拓展问题》。
时空复杂度：
时间复杂度$O(m\alpha(n,m))$，空间复杂度$O(m)$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
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 c, x;
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 500000
int n, m;
struct Graph {
int head[N], nxt[M], to[M], ind;
void addedge(int a, int b) {
int q = ++ind;
to[q] = b;
nxt[q] = head[a];
head[a] = q;
}
}g, gr, tree;
int dfn[N], pa[N], id_p[N], id;
int sdom[N], idom[N], sroot[N], best[N];
void buildTree(int x) {
//printf("%d\n", x);
dfn[x] = ++id;
id_p[id] = x;
for (int j = g.head[x]; j; j = g.nxt[j]) {
if (!dfn[g.to[j]]) {
buildTree(g.to[j]);
pa[dfn[g.to[j]]] = dfn[x];
}
}
}
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;
}
vector<int> sdom_son[N];
void LengauerTarjan() {
int i, j, k, v;
for (i = 1; i <= id; ++i)
sroot[i] = sdom[i] = best[i] = i;
for (i = id; i >= 2; --i) {
for (j = gr.head[id_p[i]]; j; j = gr.nxt[j]) {
if ((v = dfn[gr.to[j]])) {
find(v);
sdom[i] = min(sdom[i], sdom[best[v]]);
}
}
sdom_son[sdom[i]].push_back(i);
sroot[i] = pa[i];
for (j = 0; j < sdom_son[pa[i]].size(); ++j) {
find(v = sdom_son[pa[i]][j]);
if (sdom[v] == sdom[best[v]])
idom[v] = sdom[v];
else
idom[v] = best[v];
}
sdom_son[pa[i]].clear();
}
for (i = 2; i <= id; ++i) {
if (idom[i] != sdom[i])
idom[i] = idom[idom[i]];
tree.addedge(id_p[idom[i]], id_p[i]);
}
}
int siz[N];
void dfs(int x) {
siz[x] = 1;
for (int j = tree.head[x]; j; j = tree.nxt[j]) {
dfs(tree.to[j]);
siz[x] += siz[tree.to[j]];
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
n = getint();
m = getint();
int i, j, a, b;
for (i = 1; i <= m; ++i) {
a = getint();
b = getint();
g.addedge(a, b);
gr.addedge(b, a);
}
buildTree(1);
LengauerTarjan();
dfs(1);
long long ans = 0;
for (j = tree.head[1]; j; j = tree.nxt[j])
ans += (ll)siz[tree.to[j]] * (siz[1] - 1 - siz[tree.to[j]]);
ans = ans / 2 + siz[1] - 1;
cout << ans << endl;
return 0;
}
评论 (0)