Cod sursa(job #2217802)

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

}lv[100001];
int viz[100001],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[100001],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;
}