Cod sursa(job #2532078)

Utilizator danbesuDan Besu danbesu Data 27 ianuarie 2020 12:15:27
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include<fstream>
#include<stack>
#include<algorithm>
#include<vector>

using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

int n, m;
bool parcurs[100001];
vector<int>graf[100001];

void DFS(int nod){

    stack<int>s;
    s.push(nod);

    while(!s.empty()){

        int top = s.top();
        s.pop();
        if(parcurs[top] == false){

            parcurs[top] = true;
            for(int i = 0; i<graf[top].size(); ++i){
                s.push(graf[top][i]);
            }
        }
    }
}

int main()
{
    int a, b;
    while(in>>a>>b){
        n = max(a, max(b, n));
        graf[a].push_back(b);
    }
    int nr_componente = 0;
    for(int i = 1; i<=n; ++i){
        if(parcurs[i] == false){
            ++nr_componente;
            DFS(i);
        }

    }
    out<<nr_componente;

    in.close();
    out.close();
    return 0;
}