Skip to content

Instantly share code, notes, and snippets.

@leandrovianna

leandrovianna/communication_partness.cpp

Created December 14, 2018 15:03
Show Gist options
  • Save leandrovianna/e5327b0fb1c9fe34d4aaafba2e79b449 to your computer and use it in GitHub Desktop.
Save leandrovianna/e5327b0fb1c9fe34d4aaafba2e79b449 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. leandrovianna created this gist Dec 14, 2018.
    73 changes: 73 additions & 0 deletions communication_partness.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,73 @@
    #include <bits/stdc++.h>
    using namespace std;

    const int N = 1010;
    set<int> g[N];
    bool vis[N];

    set<pair<int, int>> ss;

    void dfs(int v) {
    vis[v] = true;
    ss.insert({g[v].size(), v});

    for (const auto &u : g[v]) {
    if (vis[u] == false) {
    dfs(u);
    }
    }
    }

    int solve(int k) {
    int u;

    while (ss.size() > 0) {
    auto it = ss.begin();

    if (it->first < k) {
    u = it->second;
    ss.erase({g[u].size(), u});
    for (const auto &w : g[u]) {
    ss.erase({g[w].size(), w});
    g[w].erase(u);
    ss.insert({g[w].size(), w});
    }
    g[u].clear();

    } else {
    break;
    }
    }

    return ss.size();
    }

    int main() {
    int n, p, k, x, y;

    while (cin >> n >> p >> k, n) {
    for (int i = 0; i <= n; i++) {
    vis[i] = false;
    g[i].clear();
    }

    for (int i = 0; i < p; i++) {
    cin >> x >> y;
    g[x].insert(y);
    g[y].insert(x);
    }

    int ans = 0;
    ss.clear();
    for (int i = 1; i <= n; i++) {
    //if (vis[i] == false) {
    // ss.clear();
    // dfs(i);
    ss.insert({g[i].size(), i});
    }
    ans = solve(k);

    cout << ans << "\n";
    }
    return 0;
    }