結果

問題 No.277 根掘り葉掘り
ユーザー koyumeishikoyumeishi
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//
#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0