Cod sursa(job #2197874)

Utilizator BogdanAlexandruBogdan-Alexandru Dig BogdanAlexandru Data 22 aprilie 2018 23:34:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>

using namespace std;
FILE *f,*g;
int start[100020],t[2][400010];
int fr[100020];
void DFS(int nod)
{
    int i=start[nod];
    while(i)
    {
        if(!fr[t[0][i]])
        {
            fr[t[0][i]]=1;
            DFS(t[0][i]);
        }
        else
            i=t[1][i];
    }
}
void Rezolva(int n)
{
    int i,nr=0;
    for(i=1;i<=n;i++)
        if(!fr[i])
            DFS(i),nr++;
    fprintf(g,"%d",nr);
}
int main()
{
    f=fopen("dfs.in","r");
    g=fopen("dfs.out","w");
    int m,n,i,k=1,x,y;
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        t[0][k]=y;
        t[1][k]=start[x];
        start[x]=k;
        k++;
        t[0][k]=x;
        t[1][k]=start[y];
        start[y]=k;
        k++;
    }
    Rezolva(n);
    fclose(f),fclose(g);
    return 0;
}