Cod sursa(job #2433845)
Utilizator | Biciusca Matei matei123 | Data | 29 iunie 2019 14:13:27 |
---|---|---|---|
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;
ifstream f("dfs.in"); ofstream g("dfs.out");
int n,m,nrcomp=0;
vector <int> vecini[100005];
bool viz[100005] ;
void DFS(int x)
{ viz[x]=1;
for(int i=0; i<vecini[x].size(); i++)
if(viz[vecini[x][i]] == 0) DFS(vecini[x][i]);
}
int main()
{ f>>n>>m;
int x, y;
for(int i=1;i<=m;i++)
{ f>>x>>y ;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
for(int i=1; i<=n; i++)
{ if(viz[i] == 0)
{ nrcomp++;
DFS(i) ;
}
}
g<<nrcomp;
return 0;
}