Cod sursa(job #1113470)

Utilizator simpleBereczki Cristian simple Data 20 februarie 2014 17:00:31
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;

FILE *f=fopen("dfs.in","r"),*g=fopen("dfs.out","w");
typedef struct nod{int x;nod *urm;} *Tnod;
Tnod v[10005];
int viz[10005],n,m,cnt;

void add(Tnod &p,int val)
{
    Tnod q;
    q=new nod;
    q->x=val;
    q->urm=p;
    p=q;
}
void DFS(int val)
{
    Tnod p;
    viz[val]=1;
    for(p=v[val];p!=NULL;p=p->urm)
    {
        if(viz[p->x]==0)
        {
            DFS(p->x);
        }
    }
}
int main()
{
    fscanf(f,"%d %d",&n,&m);
    int i,x,y;
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        add(v[x],y);
        add(v[y],x);
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            cnt++;
            DFS(i);
        }
    }

    fprintf(g,"%d\n",cnt);
    fclose(f);
    fclose(g);
    return 0;
}