Cod sursa(job #3230035)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 18 mai 2024 21:04:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>

#define NMAX 100000

#define VISITED 1
#define NOTVISITED 0


void dfs(int source, std::vector<int> adj[NMAX], int vis[])
{
    vis[source] = VISITED;

    for (auto neigh : adj[source])
        if (vis[neigh] ==  NOTVISITED)
            dfs(neigh, adj, vis);
}

int main()
{
    std::ifstream fin("dfs.in");
    std::ofstream fout("dfs.out");

    int n, m;
    std::vector<int> adj[NMAX];
    int vis[NMAX] = {NOTVISITED};
    int nr = 0;


    fin >> n >> m;

    for (int v, w, i = 0; i < m; ++i) {
        fin >> v >> w;
        --v;
        --w;
        adj[v].push_back(w);
        adj[w].push_back(v);
    }

    for (int i = 0; i < n; ++i)
        if (vis[i] == NOTVISITED) {
            dfs(i, adj, vis);
            ++nr;
        }


    fout << nr << '\n';

    fin.close();
    fout.close();

    return 0;
}