Cod sursa(job #2841518)

Utilizator ilies_andrei-cristianIlies Andrei-Cristian ilies_andrei-cristian Data 29 ianuarie 2022 20:25:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,nr,viz[100002];
vector <int> Q[100002];
stack <int> st;
int main(){
    f>>n>>m;
    for(int x,y,i=1;i<=m;++i){
        f>>x>>y;
        Q[x].push_back(y);
        Q[y].push_back(x);
    }
    for(int i=1;i<=n;++i){
        if(!viz[i]){
            ++nr;
            st.push(i);
            viz[i]=1;
            while(!st.empty()){
                int k=st.top();
                bool ok=false;
                vector <int> :: iterator it=Q[k].begin(), sf=Q[k].end();
                for(;it!=sf && !ok;++it)
                    if(!viz[*it]){
                       st.push(*it);
                       viz[*it]=1;
                       ok=true;
                }
                if(!ok)
                    st.pop();
            }
        }
    }
    g<<nr<<endl;
    f.close();
    g.close();
    return 0;
}