Cod sursa(job #3146624)

Utilizator patrick_burasanPatrick Burasan patrick_burasan Data 21 august 2023 21:49:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
#include <vector>
#define pb push_back

using namespace std;

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

int const NMAX = 1e5 + 1;
int N, M, u, v, cc;
bool vis[NMAX];
vector < int > adj[NMAX];

void dfs(int node) {
    vis[node] = true;
    for (auto u : adj[node])
        if (!vis[u])
            dfs(u);
}

int main() {
    fin >> N >> M;
    while (M--) {
        fin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for (int i = 1; i <= N; i++)
        if (!vis[i]) { cc++; dfs(i); }
    fout << cc << '\n';
    fin.close();
    fout.close();
    return 0;
}