Cod sursa(job #2662355)

Utilizator miramaria27Stroie Mira miramaria27 Data 23 octombrie 2020 22:12:12
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <list>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
void dfs(int start, list<int> ad[],int visited[])
{


    visited[start] = 1;
    for(auto &child : ad[start])
    {
        if(visited[child] == 0)
            dfs(child,ad,visited);

    }

}
int main()
{
    int n,m,start;
    fin>>n>>m;
    list <int> ad[n+1];

    for(int i = 0; i < m; i ++)
    {

        int x,y;
        fin >> x >> y;
        ad[x].push_back(y);

    }
    int visited[n+1]= {0};

    int ok;
    int comp = 0;
    start = 1;
    do
    {

        ok = 0;
        comp++;
        dfs(start,ad,visited);
        for(int i=1; i<=n && ok == 0; i++)
            if(visited[i] == 0)
            {
                start = i;
                ok = 1;
            }
    }
    while(ok);
    fout<<comp;
    return 0;
}