Cod sursa(job #2202626)

Utilizator daniel.vbVasile Daniel daniel.vb Data 9 mai 2018 15:59:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>

struct muchie{
    int i;
    int j;
};

int n,m,nv[100005],lv[400005],vizitat[100005],nrcomp;
muchie mx[200005];



void schimba(int &a,int &b)
{
    int aux;
    aux=a; a=b; b=aux;
}


int vecin(int i,int k)
{
    if(mx[k].i==i)
        return mx[k].j;
    return mx[k].i;
}

void dfsc(int i)
{

    int j,k;
    vizitat[i]=1;
//    printf("%d ",i);
    for(k=nv[i]+1;k<=nv[i+1];k++)
    {
        j=vecin(i,lv[k]);
        if(vizitat[j]==0)
            dfsc(j);
    }
}

int main()
{
    int i,j,k;
    FILE *f,*g;

    f=fopen("dfs.in","r");
    g=fopen("dfs.out","w");

    fscanf(f,"%d%d",&n,&m);


    for (k=1;k<=m;k++)
    {
        fscanf(f,"%d%d",&i,&j);
        nv[i]++;nv[j]++;
        mx[k].i=i;mx[k].j=j;
    }
    for(i=2;i<=n;i++)
        nv[i]+=nv[i-1];
    for(k=1;k<=m;k++)
    {
        i=mx[k].i;
        j=mx[k].j;
        lv[nv[i]--]=k;
        lv[nv[j]--]=k;
    }
    nv[n+1]=2*m;

    for(i=1;i<=n;i++)
    {
        if(vizitat[i]==0)
        {
            nrcomp++;
  //          printf("\n");
            dfsc(i);
        }
    }
    fprintf(g,"%d",nrcomp);

}