Cod sursa(job #885998)

Utilizator alexandru93moraru alexandru sebastian alexandru93 Data 22 februarie 2013 16:31:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
#include<vector>
#define maxn 100000

using namespace std;

int N,M;

vector<bool> Viz;
vector<vector<int> > V;

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

void add(int x,int y){
    V[x].push_back(y);
    V[y].push_back(x);
}

void citire(){
    int x,y;
    f>>N>>M;
    Viz.resize(N+1);
    V.resize(N+1);
    for(int i=1;i<=M;i++){
        f>>x>>y;
        add(x,y),add(y,x);
    }
}

void parcurgereAdancime(int nod){
    Viz[nod]=true;
    for(vector<int>::iterator it=V[nod].begin();it!=V[nod].end();it++)
        if(!Viz[*it])
            parcurgereAdancime(*it);
}

int main(){
    int nrCC=0;
    citire();
    for(int i=1;i<=N;i++)
        if(!Viz[i])
            parcurgereAdancime(i),nrCC++;
    g<<nrCC<<'\n';
    return 0;
}