結果
問題 | No.2536 同値性と充足可能性 |
ユーザー |
|
提出日時 | 2023-08-15 12:51:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 2,316 bytes |
コンパイル時間 | 3,753 ms |
コンパイル使用メモリ | 273,180 KB |
実行使用メモリ | 20,668 KB |
最終ジャッジ日時 | 2024-12-14 02:25:07 |
合計ジャッジ時間 | 6,329 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/dsu> using namespace std; using namespace atcoder; int main() { int n, m; cin >> n >> m; assert(2 <= n && n <= 100000); assert(1 <= m && m <= min(100000, n * (n - 1))); vector<pair<int, int>> same, notsame; for (int i = 0; i < m; i++) { int x, y; string e; cin >> x >> e >> y; x--; y--; if (e == "<==>") same.push_back({x, y}); else notsame.push_back({x, y}); } dsu uf(n); // 「同じ」の要望についてUnionFindの辺を張る for (auto i: same) { uf.merge(i.first, i.second); } // 「同じ」の連結成分に「違う」がある場合はだめ for (auto i: notsame) { if (uf.same(i.first, i.second)) { cout << "No\n"; return 0; } } // 連結成分を求める auto gr = uf.groups(); int ns = gr.size(); vector<vector<int>> lds(ns); map<int, int> ld; // 頂点→leaderの番号 for (int i = 0; i < ns; i++) { lds[i] = gr[i]; for (int j: gr[i]) ld[j] = i; } // 「違う」の辺を張る vector<vector<int>> g(ns); for (auto i: notsame) { int ldx = ld[i.first], ldy = ld[i.second]; g[ldx].push_back(ldy); g[ldy].push_back(ldx); } // 二部グラフ判定 vector<int> col(ns, -1); for (int u = 0; u < ns; u++) { if (col[u] != -1) { continue; } col[u] = 0; queue<int> q; q.push(u); while (!q.empty()) { int v = q.front(); q.pop(); for (auto nv : g[v]) { if (col[nv] != -1) { if (col[nv] == col[v]) { cout << "No\n"; return 0; } continue; } col[nv] = 1 - col[v]; q.push(nv); } } } vector<int> c0, c1; for (int i = 0; i < n; i++) { if (col[ld[i]]) c1.push_back(i + 1); else c0.push_back(i + 1); } cout << "Yes\n"; if (c0.size() * 2 >= n) { int c0s = c0.size(); cout << c0s << '\n'; for (int i = 0; i < c0s - 1; i++) { cout << c0[i] << ' '; } cout << c0[c0s - 1] << '\n'; } else { int c1s = c1.size(); cout << c1s << '\n'; for (int i = 0; i < c1s - 1; i++) { cout << c1[i] << ' '; } cout << c1[c1s - 1] << '\n'; } }