【图论模板】图的连通分量

 

#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
static const int MAX=100000;
static const int NIL=-1;

int n;
vector<int>G[MAX+1];
int color[MAX+1];

void dfs(int cur,int c)//搜索并进行染色 
{
	stack<int>S;
	S.push(cur);
	color[cur]=c;
	while(!S.empty()){
		int t=S.top();
		S.pop();
		for(int i=0;i<G[cur].size();i++){
			int pt=G[cur][i];
			if(color[pt]==NIL)//如果没有染色
			{
				S.push(pt);
				color[pt]=c;
			} 
		}
	}
}

void assignColor(){
	int col=1;
	for(int i=0;i<n;i++)color[i]=NIL;//初始化颜色
	
	for(int i=0;i<n;i++)
		if(color[i]==NIL)dfs(i,col++); 
}

int main(){
	int s,t,m,q;
	
	cin>>n>>m;
	
	//存图（邻接表） 
	for(int i=0;i<m;i++){
		cin>>s>>t;
		G[s].push_back(t);
		G[t].push_back(s);
	}
	
	assignColor();//染色 
	
	cin>>q;
	
	for(int i=0;i<q;i++){
		cin>>s>>t;
		if(color[s]==color[t])
		{
			puts("Y");
		}
		else puts("N");
	}
	return 0;
}

/*
input:
10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3
*/