Cod sursa(job #911314)

Utilizator Sm3USmeu Rares Sm3U Data 11 martie 2013 15:24:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <vector>
#include <queue>

#define nMax 100010

using namespace std;

vector <int> graf[nMax];

int n;
int viz[nMax];
int nr;


void dfs(int nod){
    viz[nod] = 1;
    for(unsigned int i = 0; i < graf[nod].size(); ++ i){
        if(viz[graf[nod][i]] == 0){
            dfs(graf[nod][i]);
        }
    }
}

void citire(){
    int m;
    scanf("%d %d", &n, &m);
    while(m --){
        int i;
        int j;
        scanf("%d %d", &i, &j);
        graf[i].push_back(j);
        graf[j].push_back(i);
    }
}

int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    citire();
    for(int i = 1; i <= n; ++ i){
        if(viz[i] == 0){
            nr ++;
            dfs(i);
        }
    }
    printf("%d", nr);

    return 0;
}