Cod sursa(job #1811791)

Utilizator AlexBlagescuBlagescu Alex George AlexBlagescu Data 21 noiembrie 2016 16:37:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("dfs.in"); ofstream g("dfs.out");
int N, M, nr;
bool 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] = true;
            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';
    return 0;
}