Cod sursa(job #2388550)
Utilizator | Data | 26 martie 2019 10:18:31 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.6 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("listavecini.in");
ofstream out("listavecini.out");
#define NMAX 100001
vector <int>v[NMAX];
int seen[100001],cnt;
void dfs(int i){
seen[i]=1;
for(int j=0;j<v[i].size();j++){
if(!seen[v[i][j]])
dfs(v[i][j]);
}
}
int main()
{
int n,m;
in>>n>>m;
int x,y;
while(in>>x>>y){
v[x].push_back(y);
v[y].push_back(x);
}
seen[0]=1;
for(int i=1;i<=n;i++){
if(!seen[i]){
dfs(i);
cnt++;
}
}
out<<cnt;
return 0;
}