Cod sursa(job #1624205)

Utilizator SchopenhauerIordache Stefan Schopenhauer Data 2 martie 2016 09:19:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<iostream>
#include<fstream>
#include<cstdlib>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,x,y,viz[100005];
int *a[100005];

void dfs(int nod, int k)
      { int i;
        viz[nod]=k;
        for (i=1;i<=a[nod][0];i++)
            if (viz[a[nod][i]]==0)
                dfs(a[nod][i],k);}

int main()
      { int k=0,i;
       f>>n>>m;
       for (i=1;i<=n;i++)
          { a[i]=(int *) realloc (a[i],sizeof(int));
            a[i][0]=0;}
       for (i=1;i<=m;i++)
          { f>>x>>y;
            a[x][0]++;
            a[x]=(int *) realloc (a[x],(a[x][0]+1)*sizeof(int));
            a[x][a[x][0]]=y;
            a[y][0]++;
            a[y]=(int *) realloc (a[y],(a[y][0]+1)*sizeof(int));
            a[y][a[y][0]]=x;}
      for (i=1;i<=n;i++)
          if (viz[i]==0)
              dfs(i,++k);
      g<<k;
      return 0;}