Cod sursa(job #3298034)

Utilizator Victor5539Tanase Victor Victor5539 Data 26 mai 2025 13:09:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

const int MAX=1e5;
int i,n,sol,m,nod1,nod2;
vector <int> muchii[MAX+5];
bool viz[MAX+5];

void dfs(int nod)
{
    viz[nod]=1;
    for (auto x: muchii[nod])
        if (!viz[x])
            dfs(x);
}

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

    while (m)
    {
        fin>>nod1>>nod2;
        muchii[nod1].push_back(nod2);
        muchii[nod2].push_back(nod1);
        m--;
    }

    for (i=1; i<=n; i++)
    {
        if (!viz[i])
        {
            sol++;
            dfs(i);
        }
    }

    fout<<sol;
    return 0;
}