在这个物欲横流的社会
oj冷漠无情
只有这xx还有些温度
越界就越界吧 wrong 怎么回事。。。。
给出一个图
然后给出q次询问
问是否存在v和w分别到u的路径且边不重复
在边双连通分量中 任意两点 都至少存在两条边不重复的路径
那么若u v w 在同一连通图中
则存在
若不在
则只有u在 v 和 w 中间时才存在
想一想是不是
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define rb(a) scanf("%lf", &a)
#define rf(a) scanf("%f", &a)
#define pd(a) printf("%d\n", a)
#define plld(a) printf("%lld\n", a)
#define pc(a) printf("%c\n", a)
#define ps(a) printf("%s\n", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff, maxm = , maxh = ;
int n, m, q;
int head[maxn], nex[maxm], cnt, head2[maxn], cnt2;
int pre[maxn], low[maxn], sccno[maxn], dfs_clock, scc_cnt;
int pa[maxn], anc[maxn][maxh + ], deep[maxn], instack[maxn];
int f[maxn];
stack<int> s; struct node
{
int u, v;
}Node[maxm]; void add_(int u, int v)
{
Node[cnt].u = u;
Node[cnt].v = v;
nex[cnt] = head[u];
head[u] = cnt++;
} void add(int u, int v)
{
add_(u, v);
add_(v, u);
} struct edge{
int u, v, next;
}Edge[maxm]; void add2(int u, int v)
{
Edge[cnt2].u = u;
Edge[cnt2].v = v;
Edge[cnt2].next = head2[u];
head2[u] = cnt2++;
} void tarjan(int u,int fa){
low[u] = pre[u] = ++dfs_clock;
s.push(u);
instack[u] = ;
for(int i = head[u]; i != -; i = nex[i])
{
int v = Node[i].v;
if(i == (fa ^ )) continue;
if(!pre[v])
{
tarjan(v, i);
low[u] = min(low[u], low[v]);
}
else if(instack[v])
low[u] = min(low[u], pre[v]); }
if(pre[u] == low[u])
{
scc_cnt++;
for(;;)
{
int x = s.top(); s.pop();
sccno[x] = scc_cnt;
instack[x] = ;
if(x == u) break;
}
}
} int dfs(int u, int fa)
{
for(int i = ; i < maxh; i++)
anc[u][i] = anc[anc[u][i - ]][i - ];
for(int i = head2[u]; i != -; i = Edge[i].next)
{
int v = Edge[i].v;
if(v == fa || deep[v]) continue;
anc[v][] = u;
deep[v] = deep[u] + ;
dfs(v, u);
}
} int lca(int u, int v)
{
if(deep[u] < deep[v]) swap(u, v);
for(int i = maxh; i >= ; i--)
if(deep[anc[u][i]] >= deep[v])
u = anc[u][i]; for(int i = maxh; i >= ; i--)
{
if(anc[u][i] != anc[v][i])
{
u = anc[u][i];
v = anc[v][i];
}
}
if(u == v) return u;
return anc[u][];
} int find(int x)
{
return f[x] == x ? x : (f[x] = find(f[x]));
} void init()
{
rep(i, , maxn) f[i] = i;
mem(head, -);
mem(head2, -);
mem(deep, );
dfs_clock = scc_cnt = cnt = cnt2 = ;
mem(sccno, ); mem(pre, );
mem(low, );
mem(anc, );
mem(instack, );
} int main()
{
int T;
rd(T);
while(T--)
{
init();
rd(n), rd(m), rd(q);
rap(i, , m)
{
int u, v;
rd(u), rd(v);
if(u == v) continue;
add(u, v);
}
for(int i = ; i <= n; i++) if(!pre[i]) tarjan(i, -);
rap(u, , n)
{
for(int i = head[u]; i != -; i = nex[i])
{
int v = Node[i].v;
if(sccno[u] != sccno[v])
{
add2(sccno[u], sccno[v]);
int l = find(sccno[u]), r = find(sccno[v]);
if(l == r) continue;
f[l] = r;
}
}
}
rap(i, , scc_cnt)
if(!deep[i]) deep[i] = , dfs(i, -);
rap(i, , q)
{
int u, v, w;
rd(u), rd(v), rd(w);
if(find(sccno[u]) != find(sccno[v]) || find(sccno[u]) != find(sccno[w]))
{
puts("No");
continue;
}
if(sccno[v] != sccno[w])
{
int lc = lca(sccno[v], sccno[w]);
int ans1 = lca(sccno[u], sccno[v]);
int ans2 = lca(sccno[u], sccno[w]);
int ans3 =lca(lc, sccno[u]);
if(ans3 == lc && (ans1 == sccno[u] || ans2 == sccno[u]))
{
puts("Yes");
}
else
{
puts("No");
}
}
else
{
if(sccno[u] == sccno[v] )
{
puts("Yes");
continue;
}
else
puts("No");
}
}
} return ;
}