Cod sursa(job #2798836)
Utilizator | Burac Vlad vladburac | Data | 11 noiembrie 2021 23:22:47 |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
ifstream fin( "dfs.in" );
ofstream fout( "dfs.out" );
vector <int> edges[NMAX+1];
int stare[NMAX+1];
void dfs( int a ) {
stare[a] = 1;
for( auto i : edges[a] ) {
if( stare[i] == 0 )
dfs( i );
}
}
int main() {
int n, m, a, b, nr = 0, i;
fin >> n >> m;
for( i = 0; i < m; i++ ) {
fin >> a >> b;
edges[a].push_back(b);
edges[b].push_back(a);
}
for( i = 1; i <= n; i++ ) {
if( stare[i] == 0 ) {
nr++;
dfs(i);
}
}
fout << nr;
return 0;
}