Cod sursa(job #1166319)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 3 aprilie 2014 14:33:31
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define Nmax 100009
#define pb push_back
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");

int N,M,sol,x,y;
vector < int > G[Nmax];
stack < int > st;
int inST[Nmax],viz[Nmax];

void GetCC(int S)
{
    for( inST[S]=1,st.push(S); !st.empty();)
    {
        int node = st.top();
        viz[node]=1;
        while(G[node].size()>0)
        {
            int fiu=G[node].back();
            viz[fiu]=1;
            if(!inST[fiu])st.push(fiu) , inST[fiu]=1;
            G[node].pop_back();
            G[fiu].erase(find(G[fiu].begin(),G[fiu].end(),node));
        }
        inST[st.top()]=0; st.pop();
    }
}

int main()
{
    f>>N>>M;
    for (int i=1; i<=M; ++i)
        f>>x>>y , G[x].pb(y) , G[y].pb(x);
    for (int i=1; i<=N; ++i)
      if (!viz[i])
            ++sol , GetCC(i);
    g<<sol<<'\n';
    f.close(); g.close();
    return 0;
}