Question

Buna! Ma puteti ajuta cu o rezolvare si explicate la problema asta? #441 ComponenteConexe1 Cerinţa Se dă lista muchiilor unui graf neorientat. Să se determine numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex, precum și un set de asemenea muchii. Date de intrare Fişierul de intrare componenteconexe1.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j. Date de ieşire Fişierul de ieşire componenteconexe1.out va conţine pe prima linie numărul NR de muchii ce trebuie adăugate. Fiecare dintre următoarele NR linii va conține câte o muchie x y, care trebuie adăugată pentru ca graful să devină conex. Restricţii şi precizări 1 ≤ n ≤ 100 1 ≤ i , j ≤ n în fișierul de intrare muchiile se pot repeta Exemplu componenteconexe1.in 5 1 4 3 5 2 4 componenteconexe1.out

Answer 1

Răspuns:

#include<bits/stdc++.h>

using namespace std;

ifstream in("componenteconexe1.in");

ofstream out("componenteconexe1.out");

vector<int> v[105],gata;

bool vis[105];

void dfs(int x){

vis[x]=1;

for(auto u:v[x]){

   if(!vis[u])dfs(u);

}

}

#define pb push_back

int main()

{

 int n,x,y;

 in>>n;

 while(in>>x>>y){

   v[x].pb(y);

   v[y].pb(x);

 }

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

   if(!vis[i]){

       gata.pb(i);

       dfs(i);

   }

 }

 out<<gata.size()-1<<'\n';

 for(auto u:gata){

   if(u!=1)

   out<<"1 "<<u<<'\n';

 }

return 0;

}

Explicație:

Ideea algoritmului este aceea ca de fiecare data cand gasim un varf care nu e conectat, il conectam cu toti prietenii lui posibili ruland parcurgerea grafului prin DFS (Deep First Search) si apoi facem conexiune intre aceasta componenta conexa si componenta conexa mama.

Am considerat componenta conexa mama cea care contine varful 1.

Asa ca de fiecare data cand intalnesc un varf neconectat, aflu toata componenta conexa de care apartine acesta, vizitez toate nodurile respective si apoi fac legatura intre nodul 1 si nodul pe care l-am intalnit.

E mai dificil de explicat decat de gandit, oricum...

Sper ca ai inteles, Bafta, bossss