Cod sursa(job #1749092)

Utilizator AhileGigel Frone Ahile 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;
}