Cod sursa(job #1347044)

Utilizator petiVass Peter peti Data 18 februarie 2015 19:21:41
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
//componente conexe
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
using namespace std;

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

    int N,M;
    ifs>>N>>M;

    vector<list<int > > v(N);

    for(int i=0;i<M;i++){
        int t; ifs>>t; t--;
        v[i].push_back(t);
        v[t].push_back(i);
    }


    int sol=0;

    vector<bool> m(N,false);

    for(int i=0;i<N;i++){
        if(!m[i]){ //DFS
            stack<int> s; s.push(i);
            while(!s.empty()){
                int f=s.top(); s.pop();
                if(!m[f]){
                    m[f]=true;
                    for(list<int>::iterator j=v[f].begin();j!=v[f].end();j++)
                        s.push(*j);
                }


            }
            sol++;
        }

    }
    ofs<<sol;
}