Cod sursa(job #3216286)

Utilizator popalin420@gmail.comPop Alin [email protected] Data 15 martie 2024 19:59:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>; 

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

VVI G;
VB v;
int n, m;

void ReadGraph();
void DFS(int);

int main()
{
    ReadGraph();
   // DFS(1);

    int cnt = 0;
    for (int node = 1; node <= n; ++node)
    {
        if (!v[node])
        {
            cnt++;
            DFS(node);
        }
    }

    fout << cnt;

    return 0;
}

void DFS(int x)
{
    v[x] = true;

    for (auto y : G[x])
    {
        if (v[y]) continue;
        DFS(y);
    }
}

void ReadGraph()
{
    fin >> n >> m;
    G = VVI(n + 1);
    v = VB(n + 1, false);

    int x, y;
    while (m--)
    {
        fin >> x >> y;
        G[x].emplace_back(y);
        G[y].emplace_back(x);
    }
}