Cod sursa(job #1920796)

Utilizator jason2013Andronache Riccardo jason2013 Data 10 martie 2017 10:08:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<bits/stdc++.h>
using namespace std;

const int N_MAX = 1e5 + 2;

vector<int>G[N_MAX];
bitset<N_MAX>visited;
int N, M, nr_comp;

void read()
{
    ifstream f("dfs.in");


    f >> N >> M;
    while(M--)
    {
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    f.close();
}

void dfs(int node)
{
    visited.set(node);

    for(const auto &son : G[node])
        if( !visited[son] )
            dfs( son );
}

void solve()
{
    for(int i = 1; i <= N; i ++)
        if( !visited[i] ){
            nr_comp ++;
            dfs(i);
    }
}

void write()
{
    ofstream g("dfs.out");

    g << nr_comp;

    g.close();
}

int main()
{
    read();
    solve();
    write();
    return 0;
}