Cod sursa(job #2424668)

Utilizator iliescu99andreiiliescu andrei iliescu99andrei Data 23 mai 2019 17:22:52
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>


using namespace std;
#define NMAX 100001

int conexe = 0;
vector<int> vecin[NMAX];
vector<int> vizitat;



void DFS(int s){
    cout<<s;

    vizitat[s]=1;
    for(int i=0;i<vecin[s].size();i++){
        if(vizitat[vecin[s][i]]==0)
            DFS(vecin[s][i]);
    }
}

int main() {
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    int n,m;
    int x,y;
    //cout<<"      "<<n<<" "<<m<<"     ";
    f>>n>>m;
    for(int i=0;i<n;i++){
        vizitat.push_back(0);
    }
    for(int i=0;i<m;i++){
        f>>x>>y;
        vecin[x].push_back(y);
    }

    for(int i=1;i<=n;i++){
        if(vizitat[i] == 0) {
            DFS(i);
            conexe++;
        }
    }
    g<<conexe;


    return 0;
}