Cod sursa(job #2308220)

Utilizator parsulPaul Cristian Banu-Taran parsul Data 26 decembrie 2018 17:40:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h>
#include <stdlib.h>
#define nmax 100000

int *edge[nmax],deg[nmax],n,m,isle,visited[nmax];

void df(int startVertex)
{
    int *p;
    visited[startVertex]=1;
    for(p=edge[startVertex];*p!=-1;++p)
        if(!visited[*p])
            df(*p);
}

int main()
{
    int i,x,y,isle=0;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n,&m);
    while(m)
    {
        scanf("%d %d",&x,&y);
        deg[x-1]++,deg[y-1]++;
        m--;
    }
    for(i=0;i<n;i++)
    {
        edge[i]=(int *)malloc((deg[i]+1)*sizeof(int));
        edge[i][deg[i]]=-1,deg[i]=0;
    }
    fseek(stdin,0,SEEK_SET);
    scanf("%d %d",&n,&m);
    while(m)
    {
        scanf("%d %d",&x,&y);
        x--,y--,edge[x][deg[x]++]=y,edge[y][deg[y]++]=x,m--;
    }
    for(i=0;i<n;i++)
        if(!visited[i])
    {
        isle++;
        df(i);
    }
    printf("%d ",isle);
}