Cod sursa(job #3145108)

Utilizator patrick_burasanPatrick Burasan patrick_burasan Data 12 august 2023 18:13:58
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int const SIZE = 1e3;
int N, M, X, Y, C, visited[SIZE + 5], adj[SIZE + 5][SIZE + 5];

inline void dfs(int const &node) {
    visited[node] = 1;
    for (int i = 1; i <= N; i++)
        if (adj[node][i] && !visited[i])
            dfs(i);
}

int main() {
    fin >> N >> M;
    for (int i = 0; i < M; i++) {
        fin >> X >> Y;
        adj[X][Y] = adj[Y][X] = 1;
    }

    for (int i = 1; i <= N; i++)
        if (!visited[i]) {
            C++;
            dfs(i);
        }
    fout << C << '\n';
    fin.close();
    fout.close();
    return 0;
}