Cod sursa(job #871351)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 4 februarie 2013 19:17:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <vector>

using namespace std;

#define pb push_back

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

int N, M, nr, pus[100001];
vector <int> V[100001];

void Citire()
{
    fin >> N >> M;
    int x, y;
    while(fin >> x >> y)
        V[x].pb(y), V[y].pb(x);
}

void DF(int s)
{
    pus[s] = 1;
    for(int i = 0; i < V[s].size(); i++)
        if(!pus[V[s][i]])
            DF(V[s][i]);
}

int main()
{
    Citire();
    for(int i = 1; i <= N; i++)
        if(!pus[i])
            DF(i), nr++;

    fout << nr;

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