結果
問題 |
No.2403 "Eight" Bridges of Königsberg
|
ユーザー |
![]() |
提出日時 | 2023-08-04 22:38:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,579 bytes |
コンパイル時間 | 1,798 ms |
コンパイル使用メモリ | 172,884 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-14 20:41:52 |
合計ジャッジ時間 | 3,853 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 25 WA * 6 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; class UnionFind { int n; vector<int> parent; vector<int> edgeCnt; public: UnionFind(int n_) : n(n_) { parent.resize(n); edgeCnt.resize(n, 0); iota(parent.begin(), parent.end(), 0); } int find(int x) { int y = parent[x]; if (y != parent[y]) { y = find(y); } return parent[x] = y; } void unite(int a, int b) { int x = find(a); int y = find(b); if (x != y) { parent[y] = x; edgeCnt[x] = edgeCnt[y] + 1; } else { edgeCnt[x]++; } } bool same(int a, int b) { return find(a) == find(b); } int EdgeCnt(int i) { return edgeCnt[i]; } }; int main() { int N, M; cin >> N >> M; vector<int> u(M), v(M); vector<int> inDegree(N, 0); vector<int> outDegree(N, 0); UnionFind uf(N); for (int i = 0; i < M; i++) { cin >> u[i] >> v[i]; u[i]--; v[i]--; inDegree[v[i]]++; outDegree[u[i]]++; uf.unite(u[i], v[i]); } int ans = 0; for (int i = 0; i < N; i++) { ans += abs(inDegree[i] - outDegree[i]); } int cnt = 0; for (int i = 0; i < N; i++) { if (uf.find(i) == i) { if (uf.EdgeCnt(i) > 0) { cnt++; } } } ans /= 2; cout << max({0, ans - 1, cnt - 1}) << endl; }