icpc_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/icpc_library

:heavy_check_mark: test/data_structure/aoj_1645.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1645"

#include "../../data_structure/undo_dsu.hpp"
#include "../../template/template.hpp"

struct Edge {
    int u, v, s;
};

using namespace lib;

int main() {
    int n, m;
    while (std::cin >> n >> m, !(n == 0 && m == 0)) {
        std::vector<Edge> edges(m);
        int max = -1;
        for (auto &[u, v, s] : edges) {
            std::cin >> u >> v >> s;
            u--;
            v--;
            chmax(max, s);
        }
        std::sort(all(edges), [](auto l, auto r) -> bool { return l.s > r.s; });
        std::vector g(n, std::vector<int>());
        undo_dsu uf(n);
        for (auto &[u, v, s] : edges) {
            g[u].emplace_back(v);
            g[v].emplace_back(u);
            uf.merge(u, v);
        }
        std::reverse(all(edges));
        std::vector<int> seen(n, -1);
        int now = 0;
        std::set<std::pair<int, int>> set;
        set.insert({uf.size(0), uf.leader(0)});
        rep(i, 1, max + 1) {
            std::queue<int> que;
            std::vector<int> vs;
            while (now < m) {
                auto [u, v, s] = edges[now];
                if (s != i) break;
                /*
                std::cout << i << '\n';
                std::cout << "debug: " << u << " " << v << " " << s << '\n';
                */
                std::pair<int, int> p = {uf.size(u), uf.leader(u)};
                if (set.find(p) != set.end()) set.erase(p);
                uf.undo();
                g[u].pop_back();
                g[v].pop_back();
                if (seen[u] < 0) {
                    vs.emplace_back(u);
                    set.insert({uf.size(u), uf.leader(u)});
                }
                if (seen[v] < 0) {
                    vs.emplace_back(v);
                    set.insert({uf.size(v), uf.leader(v)});
                }
                now++;
            }
            int smax = set.rbegin()->first;
            for (auto v : vs) {
                if (smax > uf.size(v)) {
                    std::pair<int, int> p = {uf.size(v), uf.leader(v)};
                    if (set.find(p) != set.end()) set.erase(p);
                    que.push(v);
                    seen[v] = 1;
                }
            }
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (auto nv : g[v]) {
                    if (seen[nv] < 0) {
                        seen[nv] = 1;
                        que.push(nv);
                    }
                }
            }
        }
        std::vector<int> ans;
        rep(i, 0, n) {
            if (seen[i] > 0) continue;
            ans.emplace_back(i + 1);
        }
        rep(i, 0, ans.size()) {
            std::cout << ans[i] << " \n"[i == (int)ans.size() - 1];
        }
    }
}
#line 1 "test/data_structure/aoj_1645.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1645"

#line 2 "data_structure/undo_dsu.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "data_structure/undo_dsu.hpp"

namespace lib {

struct undo_dsu {
  public:
    undo_dsu(int n) : n(n), data(n, -1) {}

    int leader(int a) const {
        if (data[a] < 0) return a;
        return leader(data[a]);
    }

    int size(int a) const {
        int x = leader(a);
        return -data[x];
    }

    int merge(int a, int b) {
        int x = leader(a);
        int y = leader(b);
        stack.push({x, data[x]});
        stack.push({y, data[y]});
        if (x == y) return x;
        if (size(x) < size(y)) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return x;
    }

    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    void undo() {
        assert(stack.size() >= 2);
        auto [x, xval] = stack.top();
        data[x] = xval;
        stack.pop();
        auto [y, yval] = stack.top();
        data[y] = yval;
        stack.pop();
    }

  private:
    int n;
    std::vector<int> data;
    std::stack<std::pair<int, int>> stack;
};

}  // namespace lib
#line 5 "test/data_structure/aoj_1645.test.cpp"

struct Edge {
    int u, v, s;
};

using namespace lib;

int main() {
    int n, m;
    while (std::cin >> n >> m, !(n == 0 && m == 0)) {
        std::vector<Edge> edges(m);
        int max = -1;
        for (auto &[u, v, s] : edges) {
            std::cin >> u >> v >> s;
            u--;
            v--;
            chmax(max, s);
        }
        std::sort(all(edges), [](auto l, auto r) -> bool { return l.s > r.s; });
        std::vector g(n, std::vector<int>());
        undo_dsu uf(n);
        for (auto &[u, v, s] : edges) {
            g[u].emplace_back(v);
            g[v].emplace_back(u);
            uf.merge(u, v);
        }
        std::reverse(all(edges));
        std::vector<int> seen(n, -1);
        int now = 0;
        std::set<std::pair<int, int>> set;
        set.insert({uf.size(0), uf.leader(0)});
        rep(i, 1, max + 1) {
            std::queue<int> que;
            std::vector<int> vs;
            while (now < m) {
                auto [u, v, s] = edges[now];
                if (s != i) break;
                /*
                std::cout << i << '\n';
                std::cout << "debug: " << u << " " << v << " " << s << '\n';
                */
                std::pair<int, int> p = {uf.size(u), uf.leader(u)};
                if (set.find(p) != set.end()) set.erase(p);
                uf.undo();
                g[u].pop_back();
                g[v].pop_back();
                if (seen[u] < 0) {
                    vs.emplace_back(u);
                    set.insert({uf.size(u), uf.leader(u)});
                }
                if (seen[v] < 0) {
                    vs.emplace_back(v);
                    set.insert({uf.size(v), uf.leader(v)});
                }
                now++;
            }
            int smax = set.rbegin()->first;
            for (auto v : vs) {
                if (smax > uf.size(v)) {
                    std::pair<int, int> p = {uf.size(v), uf.leader(v)};
                    if (set.find(p) != set.end()) set.erase(p);
                    que.push(v);
                    seen[v] = 1;
                }
            }
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (auto nv : g[v]) {
                    if (seen[nv] < 0) {
                        seen[nv] = 1;
                        que.push(nv);
                    }
                }
            }
        }
        std::vector<int> ans;
        rep(i, 0, n) {
            if (seen[i] > 0) continue;
            ans.emplace_back(i + 1);
        }
        rep(i, 0, ans.size()) {
            std::cout << ans[i] << " \n"[i == (int)ans.size() - 1];
        }
    }
}
Back to top page