Cod sursa(job #2549831)

Utilizator enedumitruene dumitru enedumitru Data 18 februarie 2020 05:48:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 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<<'\n'; g.close(); f.close(); return 0;
}