結果
問題 |
No.2536 同値性と充足可能性
|
ユーザー |
![]() |
提出日時 | 2023-11-10 23:12:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 1,999 bytes |
コンパイル時間 | 2,332 ms |
コンパイル使用メモリ | 209,088 KB |
最終ジャッジ日時 | 2025-02-17 21:24:25 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ int N, M, x, y; cin >> N >> M; vector<vector<pair<int, int>>> E(N); vector<int> color(N, -1); vector<vector<int>> bb, ww; vector<int> b, w; string S; vector<pair<int, int>> a, c; for (int i=0; i<M; i++){ cin >> x >> S >> y; x--; y--; if (S == "<==>") a.push_back({x, y}); else c.push_back({x, y}); } //同じ for (auto [x, y] : a){ E[x].push_back({y, 1}); E[y].push_back({x, 1}); } for (auto [x, y] : c){ E[x].push_back({y, -1}); E[y].push_back({x, -1}); } auto dfs=[&](auto self, int from, int c)->void{ if (c == 1) b.push_back(from); else w.push_back(from); for (auto [to, tp] : E[from]){ if (color[to] != -1){ if (tp == 1 && color[to] != color[from]){ cout << "No" << endl; exit(0); } else if (tp == -1 && color[to] == color[from]){ cout << "No" << endl; exit(0); } else continue; } if (tp == 1) color[to] = c; else color[to] = 1-c; self(self, to, color[to]); } }; for (int i=0; i<N; i++){ if (color[i] == -1){ color[i] = 0; dfs(dfs, i, 0); bb.push_back(b); ww.push_back(w); b.clear(); w.clear(); } } vector<int> ans; for (int i=0; i<bb.size(); i++){ if (bb[i].size() > ww[i].size()){ for (auto x : bb[i]) ans.push_back(x); } else{ for (auto x : ww[i]) ans.push_back(x); } } cout << "Yes" << endl; sort(ans.begin(), ans.end()); cout << ans.size() << endl; for (int i=0; i<ans.size()-1; i++) cout << ans[i]+1 << " "; cout << ans.back()+1 << endl; return 0; }