Cod sursa(job #2195197)

Utilizator NaritaandreiCNAINarita Andrei NaritaandreiCNAI Data 15 aprilie 2018 16:31:37
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <stdio.h>

using namespace std;

FILE *f,*g;
int v[100002],a[2][100002],fr[100002];
int m,n;
void citire()
{
    int k=0,i,j;
    fscanf(f, "%d %d", &n, &m);
    for(int l=1; l<=m; l++)
    {
        fscanf(f, "%d %d", &i, &j);
        ++k;
        a[0][k]=j;
        a[1][k]=v[i];
        v[i]=k;
        ++k;
        a[0][k]=i;
        a[1][k]=v[j];
        v[j]=k;
    }
}
void dfs(int nod)
{   int ok;
    fr[nod]=1;
    ok=v[nod];
    fr[ok]=1;
    while(ok)
    {
        fr[a[0][ok]]=1;
        ok=a[1][ok];
    }
}
int main()
{   int nr=0;
    f=fopen("dfs.in","r");
    g=fopen("dfs.out","w");
    citire();
    for(int i=1;i<=n;i++)
        if(!fr[i])
            dfs(i),nr++;
    fprintf(g,"%d",nr);
    fclose(f);
    fclose(g);
    return 0;
}