General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
66998879 Practice:
aniervs
190E - 89 GNU C++11 Time limit exceeded on test 12 3000 ms 60408 KB 2019-12-16 07:21:38 2019-12-16 07:21:38
→ Source
#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;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details