Cod sursa(job #847823)

Utilizator enedumitruene dumitru enedumitru Data 4 ianuarie 2013 15:50:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("dfs.in"); ofstream g("dfs.out");
int N , M , i , j , x , y , k, nr , ok;
bool viz[ 100002 ];
vector < int > Q[ 100002 ];
stack < int > st;
int main()
{   f >> N >> M;
    for (i = 1; i <= M; ++i)
        f >> x >> y , Q[x].push_back(y) , Q[y].push_back(x);
    vector < int > :: iterator it;
    for (i = 1; i <= N; ++i)
    {   if (!viz[i])
        {   viz[i] = true;
            st.push(i);
            while(!st.empty())
            {   k = st.top(); ok = 0;
                while(!Q[k].empty() && !ok)
                {   it = Q[k].begin();
                    if (!viz[*it])
                        {st.push(*it); viz[*it] = 1; ok = 1;}
                    Q[k].erase(it);
                }
                if (!ok) st.pop();
            }
            ++nr;
        }
    }
    g << nr << '\n';
    return 0;
}