union find とともに https://noshi91.hatenablog.com/entry/2019/07/19/180606 で述べられているデータ構造を管理することでこの問題を解きます。

次の \(3\) つの配列を持ち、更新を行います。

\[\begin{aligned} \operatorname{parent}[v]&\coloneqq v \text{ の union find 木における親}\\ \operatorname{size}[v]&\coloneqq v \text{ が union find 木の根であるとき、その木の頂点数}\\ \operatorname{next}[v]&\coloneqq v \text{ の次に列挙される頂点} \end{aligned}\]

はじめ、どの \(v\) についても \(\operatorname{parent}[v]=\operatorname{next}[v]=v,\operatorname{size}[v]=1\) です。

\(\operatorname{parent}\) と \(\operatorname{size}\) については通常の union find と同様にして更新を行います。 \(u,v\) に辺を張るクエリが来たとき、union find でも併合が行われたなら（つまり、クエリの直前で \(u,v\) が属する連結成分が異なっていたなら）、\(\operatorname{next}[u]\) と \(\operatorname{next}[v]\) を入れ替えます。

連結成分内の頂点を列挙するクエリが来たとき、無限列 \(v,\operatorname{next}[v],\operatorname{next}[\operatorname{next}[v]],\ldots\) が（ \(2\) 項目以降で）はじめて \(v\) と等しくなるまで列挙し、ソートして出力すればよいです。

時間計算量は、出力すべき合計頂点数を \(V_{\operatorname{sum}}\) として \(O(N+V_{\operatorname{sum}}\log N+Q\alpha(Q,N))\) となります。

実装は以下のようになります。 実際の提出

#include <vector>
#include <numeric>
#include <algorithm>

class enumerable_union_find {
    std::vector<unsigned long> next_vertex, uf_parent, uf_size;

    unsigned long find(unsigned long i) {
        while (i != uf_parent[i])i = uf_parent[i] = uf_parent[uf_parent[i]];
        return i;
    }

public:
    explicit enumerable_union_find(const unsigned long N) : next_vertex(N), uf_parent(N), uf_size(N, 1) {
        std::iota(begin(next_vertex), end(next_vertex), 0UL);
        std::iota(begin(uf_parent), end(uf_parent), 0UL);
    }

    void unite(unsigned long i, unsigned long j) {
        i = find(i);
        j = find(j);
        if (i == j)return;
        if (uf_size[i] < uf_size[j])std::swap(i, j);
        std::swap(next_vertex[i], next_vertex[j]);
        uf_size[i] += uf_size[j];
        uf_parent[j] = i;
    }

    std::vector<unsigned long> enumerate(unsigned long i) {
        std::vector<unsigned long> ret{i};
        auto now{i};
        while (i != next_vertex[now])ret.emplace_back(now = next_vertex[now]);
        std::sort(begin(ret), end(ret));
        return ret;
    }
};

#include <iostream>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;

    enumerable_union_find uf(N);

    int t, u, v;
    for (int i = 0; i < Q; ++i) {
        cin >> t;
        if (t == 1) {
            cin >> u >> v;
            uf.unite(u - 1, v - 1);
        } else {
            cin >> u;
            for (const auto x : uf.enumerate(u - 1))cout << x + 1 << " ";
            cout << endl;
        }
    }

    return 0;
}