NYCU K-core

README.md

Here is a code of NYCU K core code

all_new.cpp

#pragma GCC optimize(3,"Ofast", "inline")

#include <iostream>
#include <vector>
#include <deque>
#include <unordered_map>
#include <algorithm>
using namespace std;

#define all(c) c.begin() , c.end()
#define speed_up ios_base::sync_with_stdio(0) , cin.tie(0) 
#define s_int unsigned short int

vector<vector<s_int>> input_graph(2,vector<s_int>());
//pair<s_int, deque<s_int>> g;

s_int g_k;
deque<s_int> g_sb;

inline void BZ_algor() {
    //unordered_map<int, int> L, d;
    s_int in_s = input_graph.size();
    s_int max_k = NULL, d_max = NULL; //= *max_element(all(d));

    vector<s_int> L(in_s), d(in_s);
    unordered_map<s_int, vector<s_int>> D;

    for (s_int i = NULL; i < in_s; i ++) {
        s_int size_part = input_graph[i].size();//elme.second.size();


        d[i] = size_part; //elme.first
        D[size_part].emplace_back(i);// elme.first
        if (size_part > d_max) {
            d_max = size_part;
        }
    }
    
    //s_int p = NULL;
    for (s_int k = NULL; k <= d_max; k++) {
        while (!D[k].empty()) {
            s_int p = D[k].back();
            D[k].pop_back();

            L[p] = k;
            if (k >max_k) {
                max_k = k;
            }
            //max_k = max(max_k, k);

            for (auto& j : input_graph[p]) {
                if (d[j] > k) {
                    D[d[j]].erase(find(all(D[d[j]]), j));//find(D[d[j]].begin(), D[d[j]].end(), j)
                    D[d[j] - 1].emplace_back(j);
                    d[j]--;

                }
            }

        }

    }

    for (s_int i = NULL; i < in_s; i++) {
        if (L[i] == max_k) {
            g_sb.emplace_back(i);
        }
    }

    g_k = max_k;
    //  delete[] L, d;
}



int main() {
    speed_up;
    s_int a, b, m;

    while (cin >> a >> b) {
        m = max(a, b);
        if (m > input_graph.size()-1) {
            input_graph.resize(m+1, vector<s_int>());
        }
        input_graph[a].emplace_back(b);
        input_graph[b].emplace_back(a);
    }
    for (auto& elme : input_graph) {
        sort(all(elme));
    }

    BZ_algor();
    
    deque<s_int> sg_sub = g_sb;
    vector<s_int> part_int;

    cout << g_k << "-core\n";
    for (auto & i : g_sb) {
        part_int.clear();

        set_intersection(all(input_graph[i]), all(sg_sub), inserter(part_int, part_int.begin()));

        // get sub text ;
        for (auto & elme :part_int) {
            cout << i << ' ' << elme << '\n';
        }
        sg_sub.pop_front();
        
    }
    
    return 0;
}