Cod sursa(job #1391369)

Utilizator BaTDucKMocanu George BaTDucK Data 17 martie 2015 21:24:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<bits/stdc++.h>
#define Nmax 100002
#define IT vector < int > :: iterator
using namespace std;
vector < int > G[Nmax];
int N, M; bool viz[Nmax];
void Read()
{
    freopen("dfs.in", "r", stdin);
    scanf("%d%d", &N, &M);
    for( ; M; -- M) {
        int x, y;
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
void dfs(int Nod)
{
    viz[Nod] = 1;
    for(IT it = G[Nod].begin(); it != G[Nod].end(); ++ it)
        if(!viz[*it])
            dfs(*it);
}
int main()
{
    Read();
    int SOL = 0;
    for(int i = 1; i <= N; ++ i)
        if(!viz[i])
            dfs(i), ++ SOL;
    fprintf(fopen("dfs.out", "w"), "%d", SOL);
    return 0;
}