Cod sursa(job #2217806)

Utilizator Mihaibv13Mihai Stoian Mihaibv13 Data 2 iulie 2018 11:51:48
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <cstdio>
#define next(a) ++lv[a].n
using namespace std;
struct listavecini
{
   int vecin[20000],n;

}lv[20000];
int viz[20000],cc;
int main()
{
    int n,m,i,j;
    FILE *f=fopen("dfs.in","r");
    FILE *g=fopen("dfs.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {  int x,y;
        fscanf(f,"%d%d",&x,&y);
        lv[x].vecin[next(x)] = y;
        lv[y].vecin[next(y)] = x;
    }

   for(j=1;j<=n;j++)
   {

       if(viz[j]==0)
       {
           cc++;
           int st[20000],nst=0;
           st[++nst] = j;
           while(nst)
           {
               int nc = st[nst--];
               viz[nc]=1;

               for(i=1; i<=lv[nc].n;i++)
               {
                   if(viz[lv[nc].vecin[i]]==0) st[++nst]=lv[nc].vecin[i];
               }

           }
       }
   }

   fprintf(g,"%d",cc);
    return 0;
}