Cod sursa(job #1831838)

Utilizator aditzu7Adrian Capraru aditzu7 Data 18 decembrie 2016 20:47:03
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>
#include <iostream>
using namespace std;
FILE*f=fopen("dfs.in","r");
FILE*g=fopen("dfs.out","w");
int i,y,x, n,m,viz[100001];
struct nod
{
    int inf;
    nod *urm;
}*v[1000001],*c;
void adaugare(nod *&prim,int x)
{
    nod *nou;
    nou=new nod;
    nou->inf=x;
    nou->urm=NULL;
    if(prim==NULL) prim=nou;
    else
    {
        nou->urm=prim,prim=nou;
    }
}
void DF(int i,int x)
{
    viz[i]=x;
    nod *p;
    for(p=v[i]; p!=NULL; p=p->urm)
    {
        if(viz[p->inf]==0)
            DF(p->inf,x);
    }
}
int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        fscanf(f,"%d%d",&x,&y);
        adaugare(v[x],y);
        adaugare(v[y],x);

    }
    x=1;
    for(i=1; i<=n; i++)if(viz[i]==0) DF(i,x);
        else x++;
        x--;
    fprintf(g,"%d",x);
    fclose(f);
    fclose(g);
    return 0;
}