图的开始--第二天打卡之连通 分量
作者:
lgd123
,
2021-07-26 18:45:11
,
所有人可见
,
阅读 330
/*连通分量
1、对于生成树:对于一个图来说,生成树包括它所有点的,但不包括全部边。
2、对于连通分量:非连通图的极大连通子图叫连通分量,每个分量都是一个连通图
3、对于一个连通性未知的图来说,其极大连通子图即为改图的连通分量
4、注:极大连通子图和极小连通子图都是在无向图中产生的。
5、对于有向图,只有极大强连通子图。
6、对于最小生成树:即:包含全部顶点并且包含最少的点的生成树为最小生成树。
7、对于极小生成子图:一个连通图的最小生成树是该连通图顶点集确定的极小连通子图。
8、注:一个连通图中可以有不同的生成树,所以生成树不是唯一的,但最小的生成树,是唯一的,且极小连通子图只存在于连通图中。
9、连通分量可以通过深度搜索和宽度搜索来寻找。
10、对于邻接表:它储存点与点之间关系比较节省空间,但是不容易删除一条边。
*/
[(借鉴博客)更多连通分量](https://blog.csdn.net/qq_37134008/article/details/85325251)
----------
#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;
}
}
//system("pause");
return 0;
}