Mai intai trebuie sa te autentifici.
Cod sursa(job #1749092)
| Utilizator | Data | 27 august 2016 20:59:47 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.96 kb |
#include<bits/stdc++.h>
using namespace std;
#define in f
#define out g
ifstream f ("dfs.in");
ofstream g ("dfs.out");
int n;
int m;
int x;
int y;
vector <int> stl[100010];
queue <int> q;
int node;
int viz[100010];
int rez = 1;
int main() {
in >> n;
in >> m;
for(int i = 1; i <= m; i++) {
in >> x;
in >> y;
stl[x].push_back(y);
stl[y].push_back(x);
}
q.push(1);
viz[1]++;
for(int i = 1; i <= n; i++) {
while(q.empty() == false) {
node = q.front();
q.pop();
for(int j = 0; j < stl[node].size(); j++) {
if(viz[stl[node][j]] == 0) {
viz[stl[node][j]]++;
q.push(stl[node][j]);
//out << stl[node][j] << endl;
}
}
}
if(viz[i] == 0) {
q.push(i);
rez++;
}
}
out << rez;
}
