Cod sursa(job #2368268)

Utilizator AplayLazar Laurentiu Aplay Data 5 martie 2019 14:58:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <vector>
#include <stack>

#define N_MAX 100001

int N, M, components = 0, component[N_MAX];
std::vector<int> graph[N_MAX];
std::stack<int> s;

void dfs(const int start, const int componentNumber) {
    component[start] = componentNumber;
    s.push(start);
    // printf("%d -> %d\n", start, componentNumber);
    while (!s.empty()) {
        int current = s.top();
        for (int it = 0; it < graph[current].size(); ++it) {
            if (!component[graph[current][it]]) {
                component[graph[current][it]] = componentNumber;
                s.push(graph[current][it]);
                // printf("%d -> %d\n", graph[current][it], componentNumber);
                break;
            }
        }
        if (current == s.top()) s.pop();
    }
}

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

    scanf("%d%d", &N, &M);
    for (int it = 0; it < M; ++it) {
        int x, y;
        scanf("%d%d", &x, &y);
        graph[--x].push_back(--y);
        graph[y].push_back(x);
    }

    for (int it = 0; it < N; ++it) {
        if (!component[it]) {
            // printf("Starting for %d...", it);
            dfs(it, ++components);
        }
    }

    printf("%d\n", components);

    return 0;
}