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
