Cod sursa(job #840828)

Utilizator assa98Andrei Stanciu assa98 Data 23 decembrie 2012 12:24:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <cstdlib>

int cate[100100];
int *drum[100100];

int viz[100100];

int n,m;


void dfs(int k)
{
    viz[k]=1;
    for(int i=1;i<=drum[k][0];i++)
        if(!viz[drum[k][i]])
            dfs(drum[k][i]);
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    scanf("%d%d",&n,&m);

    int sp,st;

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&st,&sp);
        cate[st]++;
        cate[sp]++;
    }

    for(int i=1;i<=n;i++)
    {
        drum[i]=(int *)malloc( (cate[i]+3)*sizeof(int));
        drum[i][0]=0;
    }

    fseek(stdin,0,SEEK_SET);

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&st,&sp);
        drum[st][++drum[st][0]]=sp;
        drum[sp][++drum[sp][0]]=st;
    }

    int sol=0;
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
        {
            dfs(i);
            sol++;
        }
    }

    printf("%d",sol);
    return 0;
}