c++ grafy super wierzchołki zadanie

0

W grafie o n wierzchołkach utożsamiono niektóre wierzchołki tworząc superwierzchołki. Każdy superwierzchołek otrzymuje nazwę równą najmniejszemu numerowi wierzchołka, który wchodzi w jego skład. Napisz program, który wypisze w porządku rosnącym nazwy superwierzchołków oraz numery wierzchołków wchodzących w jego skład (te numery także powinny być wypisane w porządku rosnącym).
Wejście

W pierwszym wierszu znajdują się dwie liczby naturalne: n – liczba wierzchołków w grafie oraz m – liczba „utożsamień”. Możesz przyjąć, że n i m są nie większe od 1000000. W każdym z kolejnych m wierszy znajduje się para liczb naturalnych oznaczająca utożsamienie odpowiednich wierzchołków.
Wyjście

Wyjście powinno zawierać tyle wierszy, ile jest superwierzchołków. W i-tym wierszu powinna znaleźć się nazwa i-tego (w kolejności rosnącej) superwierzchołka, następnie znak dwukropka, a po tym znaku, numery wierzchołków wchodzące w skład superwierzchołka, wypisane w porządku rosnącym.
Uwaga:

Przyjmujemy, początkowo każdy wierzchołek jest superwierzchołkiem zawierającym samego siebie.
Przykład

Dla danych wejściowych
6 4
2 1
1 4
3 5
1 2

poprawną odpowiedzią jest
1: 1 2 4
3: 3 5
6: 6

Mój program wygląda tak i dla dwóch testów mam time limit. proszę o pomoc.

#include <iostream>
#include <vector>
#include<queue>
using namespace std;
vector<int> v[1000001];
int n,m;
queue <int> kolejka;
vector<int> wypis[1000001];
int najmniejsze;
bool od[1000001];
void wczyt();
int bfs(int k);
void wypisz();
void wyczysc();

///////////////////////////////////
int main()
{ios_base::sync_with_stdio(0);
    cin>>n>>m;
wczyt();
int p;
for(int i=1;i<=n;i++)
{p=bfs(i);
wypis[p].push_back(i);
wyczysc();
}
wypisz();
    return 0;
}
//////////////////////////////////////////

void wczyt()
{ios_base::sync_with_stdio(0);
    int a,b;
for(int o=0;o<m;o++)
{cin>>a>>b;
    v[a].push_back(b);
v[b].push_back(a);
}
}

int bfs(int k)
{
    int a,b;
  kolejka.push(k);
   od[k]=true;
   najmniejsze=k;
   while  (!kolejka.empty())
   {a=kolejka.front();
    kolejka.pop();
    for (int i=0; i<v[a].size(); i++ )
    {b=v[a][i];
	 if (!od[b])
	 { kolejka.push(b); od[b]=true;
	 if(najmniejsze>b) najmniejsze=b;
     }
    }
	}return najmniejsze;
}




void wypisz()
{for(int y=1;y<=n;y++)
{if(wypis[y].size()!=0) cout<<y<<": ";
    for (int i=0; i<wypis[y].size(); i++ )
    {
        cout<<wypis[y][i]<<" ";
}
}
}


void wyczysc()
{
    for(int u=1;u<=n;u++)
{
    od[u]=0;
}
}
0
  1. Naucz się formatować kod jak człowiek.
  2. Nie bardzo rozumiem co ten twój kod robi.
  3. Ja bym tu użył zbiorów rozłącznych union-find i całe zadanie śmignie w O(n).
  4. Klasycznie: użyłbym scanf i printf zamiast strumieni.
1

timelimit oznacza przeważnie - źle dobrany algorytm.

1 użytkowników online, w tym zalogowanych: 0, gości: 1