Cod sursa(job #2569122)

Utilizator VasAlexVasiluta Alex VasAlex Data 4 martie 2020 11:12:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>
using namespace std;
string problema = "dfs";
ifstream f(problema + ".in");
ofstream g(problema + ".out");
#ifdef INFOARENA
#define cin f
#define cout g
#endif
int n, m, i, a, b, nCon;
vector<bool> marcate;
vector<vector<int>> elem;

void dfs(int poz)
{
    marcate[poz] = 1;
    for(auto &i : elem[poz])
        if(!marcate[i])
            dfs(i);
}

int main()
{
    cin >> n >> m;
    marcate.resize(n + 2);
    elem.resize(n + 2);
    for(i = 1; i <= m; i++)
    {
        cin >> a >> b;
        elem[a].push_back(b);
        elem[b].push_back(a);
    }
    for(i = 1; i <= n; i++)
    {
        if(!marcate[i])
        {
            nCon++;
            dfs(i);
        }
    }
    cout << nCon;
    return 0;
}