Cod sursa(job #2564923)

Utilizator broaiemiupatriciu broaiemiu Data 2 martie 2020 11:05:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 100001
int vf[4*N], urm[4*N], lst[N];
int nr;
bool viz[N];
void add(int x, int y){
    vf[++nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
}
void dfs(int x)
{
    viz[x]=true;
    int p, y;
    for(p=lst[x];p!=0;p=urm[p]){
        y=vf[p];
        if(viz[y]==false)
            dfs(y);
    }
}
int main()
{
    FILE *fin, *fout;
    fin=fopen("dfs.in","r");
    fout=fopen("dfs.out","w");
    int n, m, i, rez=0;
    fscanf(fin,"%d %d",&n,&m);
    for(i=0;i<m;i++){
        int a, b;
        fscanf(fin,"%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    for(i=1;i<=n;i++){
        if(viz[i]==false){
            dfs(i);
            rez++;
        }
    }
    fprintf(fout,"%d ",rez);
    return 0;
}