Cod sursa(job #1193704)

Utilizator lucian666Vasilut Lucian lucian666 Data 1 iunie 2014 15:37:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb


#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>

using namespace std;
ofstream out("dfs.out");

#define NN 100009
#define pb push_back

vector<int>G[NN];

int n   , uz[NN] , stac[NN] ;

int rz ;

void read();
void dfs( int );

int main()
{

    read();

    for(int i=1;i<=n;i++)
        if(!uz[i])
        {
            ++rz;
            dfs(i);
        }

        out<<rz;

        return 0;
}

void read()
{

    ifstream in("dfs.in");
    int m,x,y;
    in>>n>>m;
    for(;m;m--)
    {
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void dfs( int start )
{

    uz[start ] =1 ;
    int  vf;
    vf = 1;
    stac[vf] = start;

    int root;

    while(vf)
    {

        root = stac[vf];
        int ans = -1;

        for(vector<int>::iterator I=G[root].begin();I<G[root].end();++I)
            if( !uz[*I] )
        {

            ans = *I;
            break;

        }
        if( ans  == -1 )
            --vf;
        else
        {

            stac[++vf] = ans;
            uz[ans] = 1;
        }

    }
}