Nu aveti permisiuni pentru a descarca fisierul grader_test17.in
Cod sursa(job #1194362)
| Utilizator | Data | 3 iunie 2014 17:35:51 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.74 kb |
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define maxN 100005
vector <int> list[maxN];
bool Viz[maxN];
void DFS(int nod) {
Viz[nod] = true;
for(int i = 0; i < list[nod].size(); ++ i) {
int nod2 = list[nod][i];
if(Viz[nod2]) continue;
DFS(nod2);
}
}
int main() {
ifstream f("dfs.in");
ofstream g("dfs.out");
int N, M;
f >> N >> M;
while(M --) {
int x, y;
f >> x >> y;
list[x].push_back(y);
list[y].push_back(x);
}
int nrCC = 0;
for(int i = 1; i <= N; ++ i) {
if (Viz[i]) continue;
nrCC ++;
DFS(i);
}
g << nrCC;
return 0;
}
