题解 P2097 【资料分发1】

Alex_Wei · 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很重要！