Cod sursa(job #3219480)
Utilizator | Popescu Filimon Andrei Cosmin andreifilimon | Data | 31 martie 2024 15:02:07 |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
#define MAXN 100000
vector<int> mat[MAXN+1];
bool ok[MAXN+1];
int n, m;
void dfs(int poz) {
ok[poz]=1;
for(auto i:mat[poz])
if(ok[i]==0) dfs(i);
}
int main() {
cin>>n>>m;
int i, x, y;
for(i=0; i<m; i++) {
cin>>x>>y;
mat[x].push_back(y);
mat[y].push_back(x);
}
int cnt;
cnt=0;
for(i=1; i<=n; i++)
if(ok[i]==0) {
dfs(i);
cnt++;
}
cout<<cnt;
}