Cod sursa(job #2596220)

Utilizator Claudiu_sherifStefan Claudiu Claudiu_sherif Data 9 aprilie 2020 14:28:02
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

const int NMAX=100001;
stack <int> stiva;
vector <int> graf[NMAX];
int n,m,f[NMAX];

void citire()
{
    int x,y;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        graf[x].push_back(y);
    }
}

void dfs(int a)
{
    int i;
    stiva.push(a);
    f[a]=1;
    while(stiva.empty()==false)
    {
        int node=stiva.top();
        stiva.pop();
        int p=graf[node].size();
        for(i=0;i<p;i++)
        {
            int current_node=graf[node][i];
            f[current_node]=1;
            stiva.push(current_node);
        }
    }
}

void afisare()
{
    int k=0;
    for(int i=1;i<=n;i++)
    {
        if(f[i]==0)
        {
            dfs(i);
            k++;
        }
    }
    out<<k;
}

int main()
{
    citire();
    afisare();
}