Cod sursa(job #2635564)

Utilizator richardionelRichard Ionel richardionel Data 14 iulie 2020 19:56:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;

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

vector <int> muchii[100005];
int used[100005];
int comp = 0, n, m;

void dfs(int current_nod)
{
    used[current_nod] = true;
    for (unsigned int i = 0; i < muchii[current_nod].size(); i++)
    {
        int vecin_nod = muchii[current_nod][i];
        if(used[vecin_nod] != true)
            dfs(vecin_nod);
    }
}

int main()
{
    fin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int nod1, nod2;
        fin >> nod1 >> nod2;
        muchii[nod1].push_back(nod2);
        muchii[nod2].push_back(nod1);
    }

    for (int i = 1; i <= n; i++)
    {
        if(used[i] != true)
        {
            comp++;
            dfs(i);
        }
    }
    fout << comp;
}