Cod sursa(job #942661)

Utilizator ThomasFMI Suditu Thomas Thomas Data 23 aprilie 2013 10:48:49
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

struct nod{int x;nod *urm;};
nod *p=NULL,*u=NULL;

int n,m,i,a,b;
nod *lstp[1000],*lstu[1000];

int cd[1000],v[1000],q1,q2;

void add(int inf,nod *&prim,nod *&ult)
{
    nod *tmp;
    tmp=new nod;
    tmp->x=inf;
    if(prim==NULL) prim=tmp;
    else ult->urm=tmp;
    ult=tmp;
    ult->urm=NULL;
}

void bf(int s)
{
    q1=q2=1;
    cd[q1]=s;
    v[cd[q1]]=1;
    nod *j;
    while(q1<=q2)
    {
        for(j=lstp[cd[q1]];j;j=j->urm) if(v[j->x]==0) {v[j->x]=1;cd[++q2]=j->x;}
        q1++;
    }
}

int main()
{
    f>>n>>m;

    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        add(b,lstp[a],lstu[a]);
        add(a,lstp[b],lstu[b]);
    }

    int nr=0;
    for(i=1;i<=n;i++) if(v[i]==0) {bf(i);++nr;}
    g<<nr<<"\n";

    f.close();
    g.close();
    return 0;
}