Cod sursa(job #355961)

Utilizator csizMocanu Calin csiz Data 12 octombrie 2009 20:19:35
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <iostream>

using namespace std;

bool dfs(vector<pair<vector<int>,bool> >& v,int n){
    if(v[n].second){
        v[n].second=false;
        for(int i=0;i<v[n].first.size();i++){
            dfs(v,v[n].first[i]);
        }
        return true;
    }else{
        return false;
    }
}



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

    int m,n;
    in>>n>>m;

    vector<pair<vector<int>,bool> > v;v.reserve(n);
    for(int i=0;i<n;i++){
        v.push_back(pair<vector<int>,bool>(vector<int>(),true));
    }
    for(int i=0;i<m;i++){
        int x,y;
        in>>x>>y;
        v[x-1].first.push_back(y-1);
    }

    int max=0;
    for(int i=0;i<n;i++){
        if(dfs(v,i)) max++;
    }
    out<<max;
}