Cod sursa(job #1825457)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 9 decembrie 2016 10:44:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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], pas[100001], nrcomp;
struct muchie
{
    int x, y;
}mu[200001];
void dfs(int32_t i)
{
    ///varianta recursiva
    viz[i]=1;
    ///vizitezi nodul curent
    ///alegi primul fiu nevizitat, apoi primul fiu al primului fiu nevizitat
    ///ma intorc recursiv cand intr-un nod nu mai am fii nevizitati
    ///la iesire din functie vizitezi toate nodurile unei componente conexe
    int32_t j;
    for(j=cap[i]; j<cap[i+1]; j++)
        if(!viz[v[j]]) dfs(v[j]);
}
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++;dfs(i);}///faci cate o parcurgere de la capat pt fiecare nod neviz
   f2<<nrcomp;
    return 0;
}