Cod sursa(job #2926284)

Utilizator 11111theodorSebastian Theodor-Ioan 11111theodor Data 17 octombrie 2022 17:04:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <bitset>
#include <fstream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

const int oo = 2e9;

vector <int> L[100001];
vector<vector<int>> cc;
bitset<100001> viz;
int n, m, nr_cc;

void DFS(int nod)
{
    viz[nod] = 1;
    //cc[nr_cc].push_back(nod);
    for (auto next : L[nod])
        if (!viz[next])
            DFS(next);
}

int main()
{
    ifstream fin ("dfs.in");
    ofstream fout ("dfs.out");
    fin >> n >> m;
    while (m--)
    {
        int x, y;
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    //cc.push_back({});
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0)
        {
            nr_cc++;
            //cc.push_back({});
            DFS(i);
        }
    fout << nr_cc << "\n";
    /*for (int i = 1; i <= nr_cc; i++, fout << "\n")
        for (auto it : cc[i])
            fout << it << " ";*/
    return 0;
}