# ARC176-C Max Permutation

2056diff
https://atcoder.jp/contests/arc176/tasks/arc176_c

## 解法

多重集合$S_{j}$を$S_{j} = \{ C_{x}\ |\ A_{x} = j\ \lor B_{x} = j\ \}$とする

$M$個の条件から、いくつかの添字は値が確定することがわかる。
- $S_{j}$に値$c$が２つ以上入っているならば、$P_{j} = c$でなければならない
- $S_{j}$の種類数が$2$以上であるとき、$j$に隣接している頂点のうちいくつかの値が確定する
- $P_{j}\le\min S_{j}$を満たす必要があるので、$\min S_{j}\lt c$を満たすような$j$と接続している辺はもう一方が$c$になる
- $P_{A_{i}}$の値が既に$C_{i}$以外で確定しているならば、$P_{B_{i}} = C_{i}$である。逆も然り。

BFSチックに確定している値をすべて埋めると、残りは頂点数$2$の連結成分または頂点数$1$の連結成分のみが残る。

ここにまだ未確定の値を埋める通り数を求めるのはあまり難しくない

## 実装

#include <bits/stdc++.h>

const long long MOD{998244353};

void bye() {
    std::cout << 0 << '\n';
    std::exit(0);
}

long long mult(long long l, long long r) {
    return l * r %  MOD;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N, M;
    std::cin >> N >> M;
    std::vector<int> A(M), B(M), C(M);
    std::vector<int> lower(N, N - 1);
    std::vector<std::vector<std::pair<int, int>>> g(N);
    for (int i{} ; i < M ; i++) {
        std::cin >> A[i] >> B[i] >> C[i];
        A[i]--;
        B[i]--;
        C[i]--;
        lower[A[i]] = std::min(lower[A[i]], C[i]);
        lower[B[i]] = std::min(lower[B[i]], C[i]);
        g[A[i]].push_back(std::pair{ B[i], C[i] });
        g[B[i]].push_back(std::pair{ A[i], C[i] });
    }
    std::vector<int> only(N, -1);
    std::vector<bool> used(N);
    auto push{[&](int i, int v) -> void {
        assert(0 <= i and i < N);
        assert(0 <= v and v < N);
        if (only[i] == v) return;
        if (only[i] != -1) bye();
        if (used[v]) bye();
        if (lower[i] < v) bye();
        used[v] = true;
        only[i] = v;
    }};
    for (int i{} ; i < N ; i++) {
        std::vector<int> app;
        for (auto [_, c] : g[i]) app.push_back(c);
        std::sort(app.begin(), app.end());
        for (int j{}, k{} ; j < (int)app.size() ; j = k) {
            while (k < (int)app.size() and app[j] == app[k]) k++;
            if (k - j > 1) {
                push(i, app[j]);
            }
        }
        for (auto [j, c] : g[i]) if (c != app.front()) push(j, c);
    }
    std::queue<int> que;
    for (int i{} ; i < N ; i++) if (only[i] != -1) que.push(i);
    while (que.size()) {
        int v{que.front()};
        que.pop();
        assert(only[v] != -1);
        for (auto [x, c] : g[v]) {
            if (only[x] == -1 and only[v] != c) {
                push(x, c);
                que.push(x);
            }
        }
    }
    long long ans{1};
    for (int i{} ; i < M ; i++) {
        if (only[A[i]] == C[i] or only[B[i]] == C[i]) continue;
        int cnt{(only[A[i]] == -1) + (only[B[i]] == -1)};
        assert(cnt == 0 or cnt == 2);
        if (cnt == 2) {
            assert(lower[A[i]] == lower[B[i]]);
            push(B[i], C[i]);
            ans = mult(ans, 2);
        }
    }
    std::vector<int> ok(N);
    for (int i{} ; i < N ; i++) if (only[i] == -1) ok[lower[i]]++;
    for (int i{N - 2} ; i >= 0 ; i--) ok[i] += ok[i + 1];
    int cnt{};
    for (int i{N - 1} ; i >= 0 ; i--) if (!used[i]) {
        ans = mult(ans, ok[i] - cnt);
        cnt++;
    }
    std::cout << ans << '\n';
}

[提出](https://atcoder.jp/contests/arc176/submissions/58526908)

## 感想

とくになし