Cod sursa(job #2594607)

Utilizator RazorBestPricop Razvan Marius RazorBest Data 6 aprilie 2020 13:49:22
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 100000

void dfs(int node, std::vector<int> *adj, char *visited) {
    for (int i = 0; i < adj[node].size(); i++) {
        if (!visited[adj[node][i]]) {
            visited[adj[node][i]] = 1;
            dfs(i, adj, visited);
        }
    }
}

int main() {
    std::vector<int> adj[NMAX + 1];
    int n, m, x, y, cnt = 0;
    char visited[NMAX + 1];
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    scanf("%d%d", &n, &m);
    memset(visited, 0, (n + 1) * sizeof(char));

    while (m--) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0) {
            dfs(i, adj, visited);
            cnt++;
        }
    }

    printf("%d", cnt);
}