Cod sursa(job #1825449)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 9 decembrie 2016 10:27:20
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <stdint.h>
using namespace std;
fstream f1("dfs.in", ios::in);
fstream f2("dfs.out", ios::out);
///ai un graf neorientat cu n noduri si m muchii
///sa se det numarul de componente conexe ale grafului
///poti afla asta facand dfs-uri succesive pentru nodurile nevizitate
int32_t n, m,  v[200001], cap[100001], viz[100001],  stiva[100001], vf=1, pas[100001], nrcomp;
struct muchie
{
    int x, y;
}mu[200001];
void dfs(int32_t x)
{
    ///varianta iterativa
    int32_t i;///i =indice care se plimba prin v
    ///cauti primul fiu al lui x, apoi primul fiu al fiului ales al lui x...
    while(vf!=0)
    {
        i=cap[x];

        while((i<cap[x+1])&&(viz[v[i]])) i++;///incerci sa gasesti primul fiu nevizitat

          if(i==(cap[x+1])) vf--;///daca nu ai gasit niciun fiu te intorci recursiv
          else
          {
            vf++;
            stiva[vf]=v[i];
            viz[v[i]]=nrcomp;
          }
    }
}
int main()
{
    int32_t i, x, y;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y;
        mu[i].x=x;
        mu[i].y=y;
        ///pas[i] memo provizoriu numarul de fii ai lui i
        pas[x]++;
        pas[y]++;
    }
    cap[1]=1;
    for(i=1; i<=n; i++)
        {
         cap[i+1]=cap[i]+pas[i];
         pas[i]=cap[i];
        }
   pas[1]=1;
   for(i=1; i<=m; i++)
   {
      x=mu[i].x;
      y=mu[i].y;
      v[pas[x]]=y;
      pas[x]++;
      v[pas[y]]=x;
      pas[y]++;
   }
   ///ai creat lista de adiacenta

   ///faci dfs-ul
  for(i=1; i<=n; i++)
      if(!viz[i]) {nrcomp++;vf=1;stiva[vf]=i;viz[i]=nrcomp;dfs(i);}
   f2<<nrcomp;
    return 0;
}