P2097 资料分发 1

题目描述

有一些电脑，一部分电脑有双向数据线连接。

如果一个电脑得到数据，它可以传送到的电脑都可以得到数据。

现在，你有这个数据，问你至少将其输入几台电脑，才能使所有电脑得到数据。

输入格式

第一行两个整数 $n,m$。$n$ 是点数，$m$ 是边数。

接下来 $m$ 行，每行 $2$ 个整数 $p,q$，表示 $p$ 到 $q$ 有一条双向数据线。

输出格式

一个整数，表示至少输入的电脑数量。

输入输出样例 #1

输入 #1

4 5
1 2
1 3
2 3
2 1
3 4

输出 #1

1

说明/提示

对于 $30\%$ 的数据，$n\le 100$，$m\le 1000$。

对于 $60\%$ 的数据，$n\le 2000$。

对于 $100\%$ 的数据，$0\le n\le 10^5$，$0\le m\le 2\times 10^5$，$1\le p,q\le n$。

数据可能存在重边自环。

dfs解法

#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector <int> p[100001];
int ans;
int n,m,a,b;
int vis[100001];void dfs(int x){for(int i=0;i<p[x].size();i++){if(vis[p[x][i]]==0){vis[p[x][i]]=1;dfs(p[x][i]);}}
}int main()
{cin>>n>>m;for(int i=0;i<m;i++){cin>>a>>b;p[a].push_back(b);p[b].push_back(a);}for(int i=1;i<=n;i++){if(vis[i]==0){ans++;vis[i]=1;dfs(i);}}cout<<ans;return 0;
}