Cod sursa(job #1267779)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 20 noiembrie 2014 12:03:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>

#define pb push_back
using namespace std;

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

vector<int> v[100005];
int viz[100005];
int n, m;
int nrC;

void df(int x)
{
    viz[x] = 1;
    for (vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it)
        if (!viz[*it]) df(*it);
}
int main ()
{
    int x, y;

    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!viz[i])
        {
            df(i);
            ++nrC;
        }
    }
    fout << nrC << '\n';

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