結果

問題 No.2290 UnUnion Find
コンテスト
ユーザー applejam
提出日時 2026-02-11 18:59:24
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 327 ms / 2,000 ms
コード長 2,034 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,991 ms
コンパイル使用メモリ 382,356 KB
実行使用メモリ 14,344 KB
最終ジャッジ日時 2026-02-11 18:59:48
合計ジャッジ時間 23,864 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vmi = vector<mint>;
using vvmi = vector<vmi>;
using vvvmi = vector<vvmi>;
#define all(a) (a).begin(), (a).end()
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)

class UnionFind{
    public: 
        vector<int> m_parent;
        vector<int> m_sizes;
        set<int> ls;
        UnionFind(int n){
            rep(i, n)m_parent.push_back(i);
            rep(i, n)m_sizes.push_back(1);
            rep(i, n)ls.insert(i);
        }

        int find(int i)
        {
            if (m_parent[i] == i)
            {
                return i;
            }
            return (m_parent[i] = find(m_parent[i]));
        }

        void merge(int a, int b){
            a = find(a);
            b = find(b);
            if(a != b){
                if(m_sizes[a] < m_sizes[b])swap(a, b);
                m_sizes[a] += m_sizes[b];
                ls.erase(b);
                m_parent[b] = a;
            }
        }

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

};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q; cin >> n >> q;
    UnionFind uf(n);
    while(q--){
        int i; cin >> i;
        if(i == 1){
            int u, v; cin >> u >> v;
            uf.merge(u-1, v-1);
        }else{
            int u; cin >> u;
            u--;
            int l = uf.find(u);
            if(uf.m_sizes[l] == n){
                cout << -1 << endl;
                continue;
            }
            
            auto it = uf.ls.begin();
            if(*it == l)it++;
            cout << *it + 1 << endl;
        }
    }

    return 0;
}
0