Mai intai trebuie sa te autentifici.
Cod sursa(job #2943722)
| Utilizator | Data | 21 noiembrie 2022 16:13:56 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.7 kb |
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int NMAX = 1e5;
int n, m, i, cnt, f[2 * NMAX + 5], a, b;
vector<int> v[NMAX + 5];
void dfs(int node){
f[node] = 1;
for(auto i: v[node]){
if(!f[i])
dfs(i);
}
}
void solve(){
in >> n >> m;
for(i = 1; i <= m; ++i){
in >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for(i = 1; i <= n; ++i){
if(!f[i]){
dfs(i);
cnt++;
}
}
out << cnt;
}
int main()
{
solve();
return 0;
}
