結果
問題 |
No.1605 Matrix Shape
|
ユーザー |
![]() |
提出日時 | 2021-07-17 00:26:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 183 ms / 2,000 ms |
コード長 | 1,152 bytes |
コンパイル時間 | 1,826 ms |
コンパイル使用メモリ | 200,956 KB |
最終ジャッジ日時 | 2025-01-23 02:51:01 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; struct UnionFind { UnionFind(int n) : p(n, -1) {} int root(int u) { return p[u] < 0 ? u : p[u] = root(p[u]); } int size(int u) { return -p[root(u)]; } bool same(int u, int v) { return root(u) == root(v); } bool unite(int u, int v) { u = root(u); v = root(v); if (u == v) return false; if (p[u] > p[v]) swap(u, v); p[u] += p[v]; p[v] = u; return true; } vector<int> p; }; int main() { int n; cin >> n; UnionFind uf((int)2e5 + 1); unordered_map<int, int> mp; for (int i = 0; i < n; i++) { int h, w; cin >> h >> w; uf.unite(h, w); mp[h]--; mp[w]++; } if (uf.size(mp.begin()->first) != mp.size()) { cout << 0 << endl; exit(0); } int x = 0; for (const auto &[i, d] : mp) { x += abs(d); } if (x == 0) { cout << mp.size() << endl; } else if (x == 2) { cout << 1 << endl; } else { cout << 0 << endl; } return 0; }