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;
}
}