Cod sursa(job #2282210)
| Utilizator | Data | 13 noiembrie 2018 14:33:08 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.61 kb |
#include <bits/stdc++.h>
using namespace std;
vector<int> E[100005];
bool D[100005];
void DFS(int k){
D[k]=1;
for(auto it:E[k])
if(D[it]==0)
DFS(it);
}
int main(){
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i){
int st,dr;
scanf("%d %d",&st,&dr);
E[st].push_back(dr);
E[dr].push_back(st);
}
int ct=0;
for(int i=1;i<=n;++i){
if(D[i]==0){
++ct;
DFS(i);
}
}
printf("%d\n",ct);
return 0;
}
