Cod sursa(job #926478)

Utilizator swim406Teudan Adina swim406 Data 25 martie 2013 11:13:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#define nmax 100001
#include <vector>
#include <queue>

using namespace std;

vector <int> G[nmax];
queue <int> q;
int ok[nmax], count;

int main() {
    freopen ("dfs.in", "r", stdin);
    freopen ("dfs.out", "w", stdout);
    int N, M, i, m, a, b, x;
    scanf ("%d %d", &N, &M);
    for (i = 1; i <= M; ++i) {
        scanf ("%d %d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (i = 1; i <= N; ++i)
        if (!ok[i]) {
            ++count;
            q.push(i);
            ok[i] = 1;
            while (!q.empty()) {
                x = q.front();
                q.pop();
                m = G[x].size();
                for (int j = 0; j < m; ++j) {
                    if (!ok[G[x][j]]) {
                        ok[G[x][j]] = 1;
                        q.push(G[x][j]);
                    }
                }
            }
        }
    printf ("%d", count);
    return 0;
}