結果
問題 | No.2664 Prime Sum |
ユーザー |
|
提出日時 | 2023-11-19 18:20:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 920 bytes |
コンパイル時間 | 961 ms |
コンパイル使用メモリ | 82,412 KB |
最終ジャッジ日時 | 2025-02-17 22:34:22 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 37 |
ソースコード
// AC (recgnizing bipartite graphs by Union Find)#include <iostream>#include <vector>#include <atcoder/dsu>bool is_bipartite(const std::vector<std::vector<int>>& g) {const int n = g.size();atcoder::dsu uf(2 * n);for (int u = 0; u < n; ++u) for (int v : g[u]) {uf.merge(u, v + n);uf.merge(u + n, v);}for (int v = 0; v < n; ++v) {if (uf.same(v, v + n)) {return false;}}return true;}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, m;std::cin >> n >> m;std::vector<std::vector<int>> g(n);for (int i = 0; i < m; ++i) {int u, v;std::cin >> u >> v;--u, --v;g[u].push_back(v);g[v].push_back(u);}if (is_bipartite(g)) {std::cout << "Yes" << std::endl;} else {std::cout << "No" << std::endl;}}