图的开始--第二天打卡之连通 分量
作者:
lgd123
,
2021-07-26 18:45:11
,
所有人可见
,
阅读 330
[(借鉴博客)更多连通分量](https:
----------
#include<iostream>
#include <vector>
#include<cstring>
#include<stack>
using namespace std;
const int N = 100010;
int color[N],n,m;
int id = 1;
vector<int> G[N];
void dfs(int r ,int c)
{
stack<int> s;
s.push(r);
color[r] = c;
while(!s.empty())
{
int u = s.top();
s.pop();
for (int i = 0; i<G[u].size(); i ++)
{
int v = G[u][i];
if(color[v]==-1)
{
color[v] = c;
s.push(v);
}
}
}
}
int main()
{
int l ,r,s,t;
cin>>n>>m;
for(int i = 0;i<m;i++)
{
cin>>l>>r;
G[l].push_back(r);
G[r].push_back(l);
}
memset(color,-1,sizeof(color));
for(int i = 0;i<n;i++)
{
if(color[i]==-1)
dfs(i,id++);
}
int q;
cin>>q;
for(int i = 0;i<q;i++)
{
cin>>s>>t;
if(color[s]==color[t])
{
cout<<"yes"<<endl;
}else
{
cout<<"no"<<endl;
}
}
return 0;
}