Cod sursa(job #632925)

Utilizator AnaTudorTudor Ana Maria Mihaela AnaTudor Data 12 noiembrie 2011 15:36:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

#define DIM 100005

vector <int> g[DIM];
stack <int> st;
int start[DIM];
bool viz[DIM];
int N,M,cnt;

void read ()
{
    scanf ("%d%d",&N,&M);
    for (int i=1; i<=M; ++i)
    {
        int x,y;
        scanf ("%d%d",&x,&y);
        g[x].push_back (y);
        g[y].push_back (x);
    }
}

void df (int nod)
{
    st.push (nod); viz[nod]=1;
    while (!st.empty ())
    {
        int nod=st.top (),i;

        for (i=0; i<g[nod].size (); ++i)
        {
            int vec=g[nod][i];
            if (!viz[vec])
            {
                viz[vec]=1;
                ++start[nod];
                st.push (vec);
                break ;
            }
        }

        if (i==g[nod].size ())
            st.pop ();
    }
}

void solve ()
{
    for (int i=1; i<=N; ++i)
        if (!viz[i])
        {
            ++cnt;
            df (i);
        }

    printf ("%d",cnt);
}

int main ()
{
    freopen ("dfs.in","r",stdin);
    freopen ("dfs.out","w",stdout);

    read ();
    solve ();

    return 0;
}