Cod sursa(job #680866)

Utilizator flaviusc11Fl. C. flaviusc11 Data 16 februarie 2012 00:59:10
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<cstdio>
#define NMAX 100000
#define MMAX 200000
using namespace std;
int n,m,V[NMAX],T[2][MMAX],start[NMAX],nr;

void citire()
{
    freopen("dfs.in","r",stdin);
    int i,x,y,u=0;
    scanf("%d%d", &n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        ++u;
        T[0][u]=y;
        T[1][u]=start[x];
        start[x]=u;
        ++u;
        T[0][u]=x;
        T[1][u]=start[y];
        start[y]=u;
    }

}
void bfs(int s)
{
    int ic,sf,man, coada[NMAX];
    ic=sf=1;
    coada[ic]=s;
    V[s]=1;
    while(ic<=sf)
    {
        man=start[coada[ic]];
        while(man)
        {
            if(V[T[0][man]]==0)
             {
                 sf++;
                 coada[sf]=T[0][man];
                 V[T[0][man]]=1;
             }
             man=T[1][man];
        }
        ic++;
    }
}
void afisare()
{
    freopen("dfs.out","w",stdout);
      printf("%d ", nr );
}
int main()
{
    citire();
    for(int i=1;i<=n;++i)
      if(!V[i])
       {
           bfs(i);
           nr++;
       }
    afisare();
    return 0;
}