Cod sursa(job #1486496)

Utilizator tudorcomanTudor Coman tudorcoman Data 14 septembrie 2015 22:51:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <vector>

using namespace std;
const int maxN = 100000;

vector<int> G[maxN + 1];
bool viz[maxN + 1];
int N, M, Ans;

void dfs(int source) {
    viz[source] = 1;

    for(vector<int> :: iterator it = G[source].begin(); it != G[source].end(); ++ it)
        if(!viz[*it])
            dfs(*it);
}

int main() {

    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    int a, b;
    scanf("%d %d", &N, &M);

    for(register int i = 1; i <= M; ++ i) {
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(register int i = 1; i <= N; ++ i)
        if(!viz[i])
            dfs(i), ++ Ans;

    printf("%d\n", Ans);
    return 0;
}