Cod sursa(job #497852)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 3 noiembrie 2010 12:54:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<stdio.h>
#include<vector.h>
#include<queue.h>

#define dim 100010
#define pb push_back


vector <int> v[dim];
queue <int> q;
char a[dim];
//----------------------------------------------------------------------
void add(int x,int y)
{
     v[x].pb(y);
}
//----------------------------------------------------------------------
int n,m;
void read()
{
     int x,y;
     scanf("%d %d\n",&n,&m);
     for(int i=1 ; i<=m;i++)
     {
             scanf("%d %d\n",&x,&y);
             add(x,y);
             add(y,x);
             }
}
//----------------------------------------------------------------------
void parcurge(int i )
{
     int x,k;
     for(q.push(i) ; !q.empty() ; q.pop() )
     {
                   x = q.front();
                   for(int i=0 ; i<v[x].size() ; i++ )
                   {
                           k = v[ x ] [ i ] ;
                           if ( !a[k] )
                           {
                                q.push(k);
                                a[k]=1;
                     }
                    }
                   }
}
//----------------------------------------------------------------------
void solve()
{
     read();
     int o=0;
     for(int i=1 ; i<=n;i++)
     {
             if ( !a[i] ) 
             {
                  parcurge(i);
                  o++;
                  }
             }
     printf("%d ",o);
}//----------------------------------------------------------------------
//----------------------------------------------------------------------
int main ()
{   
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    solve();
    return 0;
}