結果

問題 No.2536 同値性と充足可能性
ユーザー Today03
提出日時 2023-11-10 22:48:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 121 ms / 2,000 ms
コード長 1,859 bytes
コンパイル時間 2,384 ms
コンパイル使用メモリ 208,264 KB
最終ジャッジ日時 2025-02-17 21:17:45
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G1(N);
    vector<pair<int, int>> G2;
    for (int i = 0; i < M; i++) {
        int a, b;
        string s;
        cin >> a >> s >> b;
        a--;
        b--;
        if (s == "<==>") {
            G1[a].push_back(b);
            G1[b].push_back(a);
        } else {
            G2.push_back(make_pair(a, b));
        }
    }
    vector<int> root(N, -1);
    for (int i = 0; i < N; i++) {
        if (root[i] == -1) {
            root[i] = i;
            queue<int> Q;
            Q.push(i);
            while (!Q.empty()) {
                int now = Q.front();
                Q.pop();
                for (int nxt : G1[now]) {
                    if (root[nxt] == -1) {
                        root[nxt] = i;
                        Q.push(nxt);
                    }
                }
            }
        }
    }
    bool ans = true;
    for (pair<int, int> p : G2) {
        if (root[p.first] == root[p.second]) {
            ans = false;
        }
    }
    if (!ans) {
        cout << "No" << endl;
    } else {
        vector<vector<int>> G3(N);
        for (pair<int, int> p : G2) {
            int a = root[p.first], b = root[p.second];
            G3[a].push_back(b);
            G3[b].push_back(a);
        }
        vector<int> state(N, -1);
        for (int i = 0; i < N; i++) {
            if (root[i] == i && state[i] == -1) {
                state[i] = 0;
                queue<pair<int, int>> Q;
                Q.push(make_pair(i, 0));
                while (!Q.empty()) {
                    int now = Q.front().first;
                    int st = Q.front().second;
                    Q.pop();
                    for (int nxt : G3[now]) {
                        if (state[nxt] == -1) {
                            state[nxt] = 1 - st;
                            Q.push(make_pair(nxt, 1 - st));
                        }
                    }
                }
            } else if (root[i] != i) {
                state[i] = state[root[i]];
            }
        }
        cout << "Yes" << endl;
        int a = accumulate(state.begin(), state.end(), 0);
        vector<int> out;
        for (int i = 0; i < N; i++) {
            if ((a * 2 >= N && state[i] == 1) || (a * 2 < N && state[i] == 0)) {
                out.push_back(i + 1);
            }
        }
        cout << out.size() << endl;
        for (int i = 0; i < (int)out.size(); i++) {
            cout << out[i] << (i + 1 == out.size() ? '\n' : ' ');
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0