Tarjan算法来解这题。无向图可以转化为有向图来解决。
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1000000001
#define ll __int64
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = ;
struct node
{
int to;
int next;
}edge[MAXN*];
stack<int>s;
int n,m,pre[MAXN],ind,low[MAXN],dfn[MAXN],vis[MAXN],pa[MAXN],ins[MAXN];
void add(int x,int y)
{
edge[ind].to = y;
edge[ind].next = pre[x];
pre[x] = ind ++;
}
int find(int x)
{
if(x != pa[x])pa[x] = find(pa[x]);
return pa[x];
}
void dfs(int rt,int k,int fa)
{
ins[rt] = ;
vis[rt] = ;
low[rt] = dfn[rt] = k;
s.push(rt);
for(int i = pre[rt]; i!=-; i=edge[i].next){
int t = edge[i].to;
if(!dfn[t] && t != fa){
dfs(t,k+,rt);
low[rt] = min(low[t],low[rt]);
}
else if(ins[rt] && t != fa){
low[rt] = min(dfn[t],low[rt]);
}
}
if(low[rt] == dfn[rt]){
while(!s.empty()){
int temp = s.top();
s.pop();
int fx = find(temp);
int fy = find(rt);
if(fx != fy){
pa[fx] = fy;
}
if(temp == rt)break;
}
}
}
int main()
{
while(cin >>n >>m){
ind = ;
for(int i = ; i <= n; i++)pa[i] = i;
memset(ins,,sizeof(ins));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(pre,-,sizeof(pre));
memset(vis,,sizeof(vis));
for(int i = ; i <= m; i++){
int x,y;
cin >>x >>y;
add(x,y);
add(y,x);
} for(int i = ; i<= n; i++){
if(!vis[i]){
dfs(i,,-);
}
} int q;
cin >>q; while(q--){
int x,y;
cin >>x >>y;
if(find(x) == find(y)){
cout<<"Yes"<<endl;
}
else {
cout<<"No"<<endl;
}
}
}
return ;
}