题目链接:ZOJ4097-Rescue the Princess
题意:
给一个图(不保证连通),然后给q个询问,每次询问为给三个点u,v,w,然后问是否存在两条路径可以分别使v到u和w到u,并且这两条路径不能有重合。
题解:
考场上想到了tarjan求桥之后缩点然后做LCA,但无奈当时只会离线的LCA。。。
首先用tarjan进行边双缩点,然后对于每个询问,以u为根判断v和w的LCA是不是u即可。
关于具体操作,因为每次建树的话复杂度要爆炸,所以单对每一个连通块建树,然后对于每次询问的时候,同时把u,LCA(u,v),LCA(u,w),LCA(v,w)四个点放入数组中进行排序,若最后两个都为u的话,即在以u为根的树中,LCA(v,w)=u。(神仙操作)
参考代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 9;
const int MAXM = 2e5 + 9;
int T, n, m, q, N;
int tot = 0, sig = 0, blockcnt = 0;
int dfn[MAXN], low[MAXN], father[MAXN], col[MAXN], block[MAXN], depth[MAXN];
int grand[MAXN][30];
stack<int> S;
vector<int> newedge[MAXN];
bool used[MAXM * 2], vis[MAXN];
struct EDGE
{
int v, nxt, lca;
} edge1[MAXM * 2], qedge[5];
int ecnt1 = 0, fir1[MAXN];
void addedge_1(int u, int v)
{
edge1[ecnt1].v = v;
edge1[ecnt1].nxt = fir1[u];
fir1[u] = ecnt1++;
}
void tarjan(int u, int Father)
{
tot++;
dfn[u] = low[u] = tot;
S.push(u);
vis[u] = 1;
father[u] = Father;
for (int i = fir1[u]; i != -1; i = edge1[i].nxt)
{
if (used[i] == 0)
{
used[i] = used[i ^ 1] = 1;
int v = edge1[i].v;
if (!dfn[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else//考虑重边
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u])
{
sig++;
while (1)
{
int temp = S.top();
S.pop();
vis[temp] = 0;
col[temp] = sig;
if (temp == u)
break;
}
}
}
void getblock(int u)
{
block[u] = blockcnt;
for (int i = fir1[u]; i != -1; i = edge1[i].nxt)
{
int v = edge1[i].v;
if (!block[v])
getblock(v);
}
}
void dfs(int u)
{
vis[u] = 1;
for (int i = 1; i <= N; i++)
grand[u][i] = grand[grand[u][i - 1]][i - 1];
for (int i = 0; i < newedge[u].size(); i++)
{
int v = newedge[u][i];
if (v != grand[u][0])
{
depth[v] = depth[u] + 1;
grand[v][0] = u;
dfs(v);
}
}
}
int lca(int x, int y)
{
if (x == y)
return x;
if (depth[x] > depth[y])
swap(x, y);
for (int i = N; i >= 0; i--)
if (depth[x] < depth[y] && depth[x] <= depth[grand[y][i]])
y = grand[y][i];
if (x == y)
return x;
for (int i = N; i >= 0; i--)
if (grand[x][i] != grand[y][i])
x = grand[x][i], y = grand[y][i];
if (grand[x][0] == 0 && grand[y][0] == 0 && x != y)
return -1;
return grand[x][0];
}
int main()
{
// freopen("in.dat", "r", stdin);
scanf("%d", &T);
while (T--)
{
scanf("%d%d%d", &n, &m, &q);
memset(col, 0, sizeof(col));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(vis, 0, sizeof(vis));
memset(used, 0, sizeof(used));
memset(fir1, -1, sizeof(fir1));
memset(block, 0, sizeof(block));
memset(depth, 0, sizeof(depth));
memset(father, 0, sizeof(father));
ecnt1 = tot = sig = blockcnt = 0;
while (!S.empty())
S.pop();
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
if (u == v)
continue;
addedge_1(u, v), addedge_1(v, u);
}
for (int i = 1; i <= n; i++)
if (!block[i])
{
blockcnt++;
getblock(i);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i, i);
for (int i = 1; i <= sig; i++)
newedge[i].clear();
for (int u = 1; u <= n; u++)
for (int i = fir1[u]; i != -1; i = edge1[i].nxt)
{
int v = edge1[i].v;
if (col[u] != col[v])
newedge[col[u]].push_back(col[v]);
}
memset(vis, 0, sizeof(vis));
depth[0] = -1;
N = floor(log(sig + 0.0) / log(2.0)) + 1;
for (int i = 1; i <= sig; i++)
{
if (!vis[i])
{
depth[i] = 0;
dfs(i);
}
}
while (q--)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
if (block[x] != block[y] || block[x] != block[z])
{
puts("No");
continue;
}
x = col[x], y = col[y], z = col[z];
if (x == y || x == z)
{
puts("Yes");
continue;
}
if (y == z)
{
puts("No");
continue;
}
int t[] = {x, lca(x, y), lca(x, z), lca(y, z)};
sort(t, t + 4, [](int x0, int y0) { return depth[x0] < depth[y0]; });
if (t[2] == x && t[3] == x)
puts("Yes");
else
puts("No");
}
}
return 0;
}