Cod sursa(job #1339187)

Utilizator Edsger.DijkstraEdsger Wybe Dijkstra Edsger.Dijkstra Data 10 februarie 2015 19:01:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN = 100010;

vector <int> Graf[MAXN];
bool Viz[MAXN];

void DFS (int nod)
{
    Viz[nod] = 1;

    vector <int> :: iterator it;
    for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it)
        if (!Viz[*it])
            DFS (*it);
}

int main()
{
    int N, M, a, b, i;
    int Ans = 0;

    in >> N >> M;
    for (i = 1; i <= M; i ++){
        in >> a >> b;

        Graf[a].push_back (b);
        Graf[b].push_back (a);
    }

    for (i = 1; i <= N; i ++)
        if (!Viz[i]){
            Ans ++;
            DFS (i);
        }

    out << Ans;

    return 0;
}