Mai intai trebuie sa te autentifici.
Cod sursa(job #2163887)
| Utilizator | Data | 12 martie 2018 20:22:12 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.78 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int NMax = 1e5 + 5;
vector< vector< int > > G(NMax);
vector< bool > viz(NMax);
vector< int > componenteConexe(NMax);
void DFS(int nod, int componentaActuala) {
viz[nod] = true;
componenteConexe[nod] = componentaActuala;
for(auto vecin: G[nod]) {
if(!viz[vecin]) {
DFS(vecin, componentaActuala);
}
}
}
int main() {
int n, m; in >> n >> m;
for(int i = 1; i <= m; ++i) {
int x, y; in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
int componentaActuala = 0;
for(int i = 1; i <= n; ++i) {
if(!viz[i]) {
DFS(i, ++componentaActuala);
}
}
out << *max_element(componenteConexe.begin(), componenteConexe.end());
in.close(); out.close();
return 0;
}