Cod sursa(job #1916804)

Utilizator duesakBourceanu Cristian duesak Data 9 martie 2017 10:24:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
bool vz[100001];
int st[100001];
vector<int>g[100001];
int main(){
    int n,m,nd,i,k=0,cc=0,a,b;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b;
        if(a!=b){g[a].push_back(b);g[b].push_back(a);}
    }
    vector<int>::iterator it;

    for(i=1;i<=n;i++){
        if(!vz[i]){++cc;st[++k]=i;vz[i]=true;}
        while(k){
            nd=st[k];k--;
            for(it=g[nd].begin();it!=g[nd].end();it++)
                if(!vz[*it]){
                        st[++k]=*it;
                        vz[*it]=true;
                        }
        }
    }
    fout<<cc<<'\n';
    fin.close();
    fout.close();
    return 0;
}