Cod sursa(job #3125936)

Utilizator seby_me14Ilinca Sebastian-Ionut seby_me14 Data 4 mai 2023 20:08:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <vector>

#define NMAX 200000

using namespace std;

int existunVisited(int visited[NMAX], int n)
{
    for (int i = 1; i <= n; ++i) {
        if (visited[i] == 0) {
            return i;
        }
    }
    return -1;
}

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

int
main() {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    int conex_comp = 0;
    vector<int> adj[n + 1];
    int nod1, nod2;
    for (int i = 0; i < m; ++i) {
        cin >> nod1 >> nod2;
        adj[nod1].push_back(nod2);
        adj[nod2].push_back(nod1);
    }
    int visited[n + 1];
    for (int i = 1; i <= n; ++i) {
        visited[i] = 0;
    }
    int start_node = existunVisited(visited, n);
    // while (start_node != -1) {
    //     dfs(visited, n, start_node, adj);
    //     start_node = existunVisited(visited, n);
    //     conex_comp++;
    // }
    for (int i = 1; i <= n; ++i) {
        if (visited[i] == 0) {
            dfs(visited, n, i, adj);
            conex_comp++;
        }
    }
    cout << conex_comp << "\n";
    return 0;
}