Cod sursa(job #1460353)

Utilizator blackoddAxinie Razvan blackodd Data 12 iulie 2015 14:27:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

int n, m, c, x, y;
vector<vector<int> > G;
queue<int>Q;
vector<bool> viz;

#define pb push_back

void Dfs(int i);

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int main()
{
    fin >> n >> m;

    G.resize(n + 1);
    viz.resize(n + 1);

    while ( m-- )
    {
        fin >> x >> y;
        G[x].pb(y);
        G[y].pb(x);
    }

    for ( int i = 1; i <= n; ++i )
        if ( !viz[i] )
    {
        c++;
        Dfs(i);
    }

    fout << c;



    fin.close();
    fout.close();
    return 0;
}

void Dfs(int i)
{
    Q.push(i);
    viz[i] = true;
    while ( !Q.empty() )
    {
    int nod = Q.front();
    Q.pop();
    for ( auto j : G[nod] )
    {
        if ( !viz[j] )
        {
            viz[j] = true;
            Q.push(j);
        }
    }
    }
}