Question

Se dau cele n-1 muchii ale unui arbore cu n noduri și un nod k . Afișați vectorul de tați al arborelui cu rădăcina în k.

arbore.in
7 4
1 2
1 4
1 7
3 7
5 7
6 7

arbore.out

4 1 7 0 7 7 1

Link pbinfo: https://www.pbinfo.ro/?pagina=probleme&id=636

Answer 1

Răspuns:

#include <iostream>

#include <fstream>

using namespace std;

ifstream f("arbore.in");

ofstream g("arbore.out");

int tata[105],n,x,y,k,a[105][105],viz[105];

void dfs(int k)

{ int i;

viz[k]=1;

for(i=1;i<=n;i++)

{

   if(viz[i]==0 && a[k][i])

   {

       tata[i]=k;

       dfs(i);

   }

}

}

int main()

{ int i;

f>>n>>k;

for(i=1;i<n;i++)

{

   f>>x>>y;

   a[x][y]=a[y][x]=1;

}

dfs(k);

viz[k]=1;

for(i=1;i<=n;i++)

   g<<tata[i]<<" ";

   return 0;

}

Explicație: