verify/aizu_online_judge/others/1645.test.cpp

View this file on GitHub
Last update: 2024-11-09 01:34:39+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/1645

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1645"
#include "../../../src/template/template.hpp"
#include "../../../src/data_structure/rollback_union_find.hpp"
struct Edge {
    int u, v, s;
};
bool comp(const Edge& e1, const Edge& e2) {
    return e1.s < e2.s;
}
int main(void) {
    while(1) {
        int n, m;
        cin >> n >> m;
        if(n == 0 and m == 0) break;
        vector<Edge> e(m);
        rep(i, 0, m) {
            cin >> e[i].u >> e[i].v >> e[i].s;
            e[i].u--;
            e[i].v--;
        }
        sort(e.begin(), e.end(), comp);
        RollbackUnionFind uf(n);
        rrep(i, m - 1, 0) {
            uf.merge(e[i].u, e[i].v);
        }
        set<int> stl;
        stl.insert(uf.leader(0));
        rep(i, 0, m) {
            int j;
            for(j = i; j < m; ++j) {
                if(e[i].s != e[j].s) break;
            }
            set<int> er, id;
            rep(k, i, j) {
                if(stl.find(uf.leader(e[k].u)) != stl.end()) {
                    er.insert(uf.leader(e[k].u));
                    id.insert(k);
                }
            }
            rep(k, i, j) {
                uf.undo();
            }
            for(const int x : er) {
                stl.erase(x);
            }
            for(const int x : id) {
                stl.insert(uf.leader(e[x].u));
                stl.insert(uf.leader(e[x].v));
            }
            int ma = 0;
            for(const int x : stl) {
                ma = max(ma, uf.size(x));
            }
            set<int> nst;
            for(const int x : stl) {
                if(uf.size(x) == ma) {
                    nst.insert(x);
                }
            }
            swap(stl, nst);
            i = j - 1;
        }
        bool flag = false;
        for(const int x : stl) {
            if(flag) cout << ' ';
            cout << x + 1;
            flag = true;
        }
        cout << '\n';
    }
}

#line 1 "verify/aizu_online_judge/others/1645.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1645"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/rollback_union_find.hpp"
struct RollbackUnionFind {
    RollbackUnionFind(const int N)
        : n(N), data(N, -1), inner_snap(0) {
    }
    int merge(const int a, const int b) {
        assert(0 <= a and a < n);
        assert(0 <= b and b < n);
        int x = leader(a), y = leader(b);
        history.emplace(x, data[x]);
        history.emplace(y, data[y]);
        if(x == y) return x;
        if(-data[x] < -data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return x;
    }
    bool same(const int a, const int b) const {
        assert(0 <= a and a < n);
        assert(0 <= b and b < n);
        return leader(a) == leader(b);
    }
    int leader(const int a) const {
        assert(0 <= a and a < n);
        if(data[a] < 0) return a;
        return leader(data[a]);
    }
    int size(const int a) const {
        assert(0 <= a and a < n);
        return (-data[leader(a)]);
    }
    void undo() {
        assert((int)history.size() >= 2);
        data[history.top().first] = history.top().second;
        history.pop();
        data[history.top().first] = history.top().second;
        history.pop();
    }
    void snapshot() {
        inner_snap = (int)history.size() / 2;
    }
    int get_state() const {
        return (int)history.size() / 2;
    }
    void rollback(int state = -1) {
        if(state == -1) state = inner_snap;
        state *= 2;
        assert(state <= (int)history.size());
        while(state < (int)history.size()) undo();
    }

   private:
    int n;
    vector<int> data;
    stack<pair<int, int>> history;
    int inner_snap;
};
#line 4 "verify/aizu_online_judge/others/1645.test.cpp"
struct Edge {
    int u, v, s;
};
bool comp(const Edge& e1, const Edge& e2) {
    return e1.s < e2.s;
}
int main(void) {
    while(1) {
        int n, m;
        cin >> n >> m;
        if(n == 0 and m == 0) break;
        vector<Edge> e(m);
        rep(i, 0, m) {
            cin >> e[i].u >> e[i].v >> e[i].s;
            e[i].u--;
            e[i].v--;
        }
        sort(e.begin(), e.end(), comp);
        RollbackUnionFind uf(n);
        rrep(i, m - 1, 0) {
            uf.merge(e[i].u, e[i].v);
        }
        set<int> stl;
        stl.insert(uf.leader(0));
        rep(i, 0, m) {
            int j;
            for(j = i; j < m; ++j) {
                if(e[i].s != e[j].s) break;
            }
            set<int> er, id;
            rep(k, i, j) {
                if(stl.find(uf.leader(e[k].u)) != stl.end()) {
                    er.insert(uf.leader(e[k].u));
                    id.insert(k);
                }
            }
            rep(k, i, j) {
                uf.undo();
            }
            for(const int x : er) {
                stl.erase(x);
            }
            for(const int x : id) {
                stl.insert(uf.leader(e[x].u));
                stl.insert(uf.leader(e[x].v));
            }
            int ma = 0;
            for(const int x : stl) {
                ma = max(ma, uf.size(x));
            }
            set<int> nst;
            for(const int x : stl) {
                if(uf.size(x) == ma) {
                    nst.insert(x);
                }
            }
            swap(stl, nst);
            i = j - 1;
        }
        bool flag = false;
        for(const int x : stl) {
            if(flag) cout << ' ';
            cout << x + 1;
            flag = true;
        }
        cout << '\n';
    }
}