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;
}