自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:33:57，当前版本为作者最后更新于2019-01-03 19:34:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：建图，dfs，记录连通块的个数

• 点数最大是100000，用二维数组空间会炸

• 看到边数只有200000，很自然地想到用不定量数组来存边

• 遍历所有的点，如果这一个点没有被访问过，连通块的个数就要+1

具体思路见代码

#include<bits/stdc++.h>
using namespace std;
vector <int> p[100100];//p[n]存储点n所连接的点
int n,m,f,s,ans,pd[100100];//ans是连通块的个数，pd数组判断这个点有没有被访问过
void dfs(int x)
{
	for(int y=0;y<p[x].size();y++)//遍历所有与x相邻的边 
		if(pd[p[x][y]]==0)//如果这个点没有被访问过 
			pd[p[x][y]]=1,dfs(p[x][y]);//标记一下，访问这一个点 
}
int main()
{
	cin>>n>>m;
	for(int x=1;x<=m;x++)
		cin>>f>>s,p[f].push_back(s),p[s].push_back(f);//存边 
	for(int x=1;x<=n;x++)
		if(pd[x]==0)
			ans++,pd[x]=1,dfs(x);//连通块的个数+1，标记并访问
	cout<<ans;//输出
	return 0;
}

学好dfs很重要！