Cod sursa(job #1007988)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 9 octombrie 2013 23:08:40
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;

struct nod
{
    int info;
    nod *urm;
};

nod *p[100005];

int n,m,viz[100005],c[100005],nr;
nod *po[100005];

inline void Citire()
{
    int i,k=1,x,y,contr=1;
    nod *prim,*p,*u;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    i=1;
    scanf("%d%d",&x,&y);
    while (i<=m)
        {
            if (x!=k)
                k=x;
            p=new nod;
            p->info=y;
            p->urm=NULL;
            u=p;
            if (i<m)
                {i++;
                 scanf("%d%d",&x,&y);
                 while (x==k && contr==1)
                 {
                    prim=new nod;
                    prim->info=y;
                    prim->urm=NULL;
                    u->urm=prim;
                    u=prim;
                    if (i<m)
                        {i++;
                         scanf("%d%d",&x,&y);
                        }
                    else contr=0;
                  }
                  po[k]=p;
                }
            else {i=m+1;po[k]=p;}
        }

}

inline void BreadhtFirst()
{
    int i,contor,v,pr,ul;
    contor=1;
    while (contor<=n && contor!=-1)
       {
           c[1]=contor;viz[contor]=1;
           pr=1;ul=1;
           nod *prim;
           while (pr<=ul)
                {
                    v=c[pr];pr=pr+1;
                    for (prim=po[contor];prim!=NULL;prim=prim->urm)
                        if (viz[prim->info]==0)
                            {
                                ul=ul+1;
                                c[ul]=prim->info;
                                viz[prim->info]=1;
                            }
                }
           nr++;
           contor=-1;
           for (i=1;i<=n && contor==-1;i++)
                if (viz[i]==0)
                    contor=i;
       }

}

int main()
{
    int i;
    Citire();
    BreadhtFirst();
    printf("%d\n",nr);
    return 0;
}