Cod sursa(job #1008390)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 10 octombrie 2013 22:18:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 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,x,y;
    nod *prim,*p,*u;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            prim=new nod;
            prim->info=y;
            prim->urm=po[x];
            po[x]=prim;
            prim=new nod;
            prim->info=x;
            prim->urm=po[y];
            po[y]=prim;
        }
}

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

inline void Rezolva()
{
    int i;
    for (i=1;i<=n;i++)
         if (viz[i]==0)
            {BreadhtFirst(i);nr++;}
}

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