C++11(clang++ 3.9) 解法, 执行用时: 623ms, 内存消耗: 21752K, 提交时间: 2020-08-15 20:14:02

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define ll long long 
using namespace std;
const int maxn=2e5+5;
int dfn[maxn],low[maxn],stack[maxn],vis[maxn],deep,top,num,s[maxn];
int n,m;

vector<int>G[maxn];
vector<int>g[maxn];
vector<int>T[maxn];

void tarjan(int u){
	dfn[u]=low[u]=++deep;
	stack[++top]=u;
	vis[u]=1;
	for (int v:G[u]){
		if (!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if (vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	
	if (low[u]==dfn[u]){
		num++;
		do{
			T[num].push_back(stack[top]);
			vis[stack[top]]=0;
			top--;
		}while (stack[top+1]!=u);

	}
}
int a[maxn],b[maxn];


int f[maxn][25], dep[maxn];
int  q;

void dfs(int now,int fa){
    dep[now]=dep[fa]+1;f[now][0]=fa;
    for(int i=1; (1<<i)<=dep[now]; i++)
        f[now][i]=f[f[now][i-1]][i-1];
        
    for(int u:g[now])
        if(u!=fa) dfs(u,now);
}

int LCA(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 22; ~i; i--) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
    if(x == y) return x;
    for(int i = 22; ~i; i--) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}



int main(){
	ios::sync_with_stdio(false);
	int N,M,t;
	cin>>N>>M>>t;
	for (int i=1;i<=M;i++){
		cin>>a[i]>>b[i];
		G[a[i]].push_back(b[i]);	
	}
	
	for (int i=1;i<=N;i++){
		if (!dfn[i]) tarjan(i);
	}
	
	for (int i=1;i<=num;i++){
		for (int j=0;j<T[i].size();j++){
			s[T[i][j]]=i;
		}
	}
	for (int i=1;i<=M;i++){
		if (s[a[i]]!=s[b[i]]){
			g[s[a[i]]].push_back(s[b[i]]);
			g[s[b[i]]].push_back(s[a[i]]);
		}
	}
	
	dfs(1,0);
	
	
	for (int i=0;i<t;i++){
		int a,b,c,d,lca1,lca2;
		cin>>a>>b>>c>>d;
		a=s[a];
		b=s[b];
		c=s[c];
		d=s[d];
		
		
		int p=LCA(a,b),q=LCA(c,d);
        if((dep[p]>dep[c]&&dep[p]>dep[d])||(dep[q]>dep[a]&&dep[q]>dep[b]))
        {
            puts("N");
            continue;
        }
        if(dep[p]>=dep[q])
        {
            if(LCA(p,c)==p||LCA(p,d)==p)
            {
                puts("Y");
                continue;
            }
        }
        else
        {
            if(LCA(q,a)==q||LCA(q,b)==q)
            {
                puts("Y");
                continue;
            }
        }
        puts("N");
		
	}
	
}