Cod sursa(job #2797926)

Utilizator MoraruLiviuMoraru Mihai-Liviu MoraruLiviu Data 10 noiembrie 2021 19:20:49
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include<bits/stdc++.h>
using namespace std;
 
ifstream f("dfs.in");
ofstream g("dfs.out");

vector <int> adiacenta[1000000];
bool deja_Vizitat[1000000];

int nrnoduri, nrmuchii, cnt;

void DFS(int nod)
{
    int i;
    deja_Vizitat[nod] = 1;
    for (int i=1; i<=nrnoduri; i++)
        if (!deja_Vizitat[adiacenta[nod][i]])
            DFS(i);
}

int main()
{

    f>>nrnoduri;
    f>>nrmuchii;

    int nod1, nod2;

    for(int i=0; i<nrmuchii; i++)
    {
        f>>nod1;
        f>>nod2;
        adiacenta[nod1].push_back(nod2);
    }

    for(int i; i<=nrnoduri; i++)
        if (!deja_Vizitat[i])
        {
            cnt++;
            DFS(i);
        }
    g<<cnt;


    return 0;
}