結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2015-07-14 02:42:22 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,284 bytes |
コンパイル時間 | 625 ms |
コンパイル使用メモリ | 71,204 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-08 07:04:52 |
合計ジャッジ時間 | 3,136 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 2 |
other | WA * 18 |
ソースコード
//入力検証用#include <iostream>#include <vector>#include "assert.h"#include <set>using namespace std;class UnionFindTree{typedef struct {int parent;int rank;}base_node;vector<base_node> node;public:UnionFindTree(int n){node.resize(n);for(int i=0; i<n; i++){node[i].parent=i;node[i].rank=0;}}int find(int x){if(node[x].parent == x) return x;else{return node[x].parent = find(node[x].parent);}}bool same(int x, int y){return find(x) == find(y);}void unite(int x, int y){x = find(node[x].parent);y = find(node[y].parent);if(x==y) return;if(node[x].rank < node[y].rank){node[x].parent = y;}else if(node[x].rank > node[y].rank){node[y].parent = x;}else{node[x].rank++;unite(x,y);}}};int main(){int n;cin >> n;assert(2<=n && n<=100000);UnionFindTree uft(n);vector<int> u(n-1), v(n-1);int num_edge = 0;int x,y;while(cin >> x >> y){num_edge++;u[num_edge] = x;u[num_edge] = y;assert(x < y);assert(1<=x && x<=100000);assert(1<=y && y<=100000);x--;y--;assert(!uft.same(x,y));uft.unite(x,y);}assert(num_edge == n-1);set<int> par;for(int i=0; i<n; i++){par.insert(uft.find(i));}assert(par.size() == 1);return 0;}