№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
66998879 |
Дорешивание:
aniervs |
190E
- 89
|
GNU C++11
|
Превышено ограничение времени на тесте 12
|
3000 мс
|
60408 КБ
|
2019-12-16 07:21:38 |
2019-12-16 07:21:38 |
|
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000002;
int n, m, nCC;
vector<int> G[maxn], CCs[maxn];
set<int> unvis;
queue<int> cola, aux;
void bfs(int u, int idCC){
cola.push(u);
unvis.erase(u);
while(!cola.empty()){
u = cola.front();
CCs[idCC].push_back(u);
cola.pop();
for(int v:unvis)
if(binary_search(G[u].begin(), G[u].end(), v) == 0){
aux.push(v);
cola.push(v);
}
while(!aux.empty()){
u = aux.front(); aux.pop();
unvis.erase(u);
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
while(m--){
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = 1; i <= n; i++){
unvis.insert(i);
sort(G[i].begin(), G[i].end());
}
for(int i = 1; i <= n; i++)
if(unvis.find(i) != unvis.end())
bfs(i,++nCC);
cout << nCC << '\n';
for(int i = 1; i <= nCC; i++){
cout << CCs[i].size() << ' ';
for(int j:CCs[i])
cout << j << ' ';
cout << '\n';
}
return 0;
}
Время: ? ms, память: ? КБ