Cod sursa(job #2534794)
Utilizator | scarlat marius marius004 | Data | 30 ianuarie 2020 22:31:09 |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.68 kb |
#include <fstream>
#include <vector>
std::ifstream f("dfs.in");
std::ofstream g("dfs.out");
const int NMAX = 100'005;
int n,m,componente,x,y;
bool visited[NMAX];
std::vector<int>L[NMAX];
void dfs(int nod){
visited[nod] = true;
for(int vecin : L[nod])
if(!visited[vecin])
dfs(vecin);
}
int main(){
f >> n >> m;
for(int i = 1;i <= m;++i){
f >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
for(int nod = 1;nod <= n;++nod){
if(!visited[nod]){
dfs(nod);
componente++;
}
}
g << componente;
return 0;
}