Cod sursa(job #1921454)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 10 martie 2017 12:46:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <bitset>

using namespace std;

ifstream f ("dfs.in");
ofstream t ("dfs.out");

bitset <100010> vaz;
vector <int> v[100010];

void dfs(int nod){
    vaz[nod]=true;
    vector <int> stack;
    stack.push_back(nod);
    while (!stack.empty()){
        int current=stack.back();
        stack.pop_back();
        for (auto i:v[current])
            if (!vaz[i])
                stack.push_back(i),
                vaz[i]=true;
    }
}

int main()
{
    int n,m,comp=0;
    f>>n>>m;
    for (int x,y,i=0;i<m;++i)
        f>>x>>y,
        v[x].push_back(y),
        v[y].push_back(x);
    for (int i=1;i<=n;++i)
        if (!vaz[i]){
            dfs(i);
            ++comp;
        }
    t<<comp;
    return 0;
}