質問編集履歴
2
ソースコードの可読性に難があったため修正しました。
test
CHANGED
File without changes
|
test
CHANGED
@@ -42,47 +42,13 @@
|
|
42
42
|
|
43
43
|
using namespace std;
|
44
44
|
|
45
|
-
#define MOD 1000000007
|
46
|
-
|
47
|
-
#define INF 1LL<<50
|
48
|
-
|
49
|
-
#define fst first
|
50
|
-
|
51
|
-
#define sec second
|
52
|
-
|
53
|
-
#define pb push_back
|
54
|
-
|
55
|
-
#define int long long
|
56
|
-
|
57
|
-
#define ALL(obj) (obj).begin(), (obj).end()
|
58
|
-
|
59
|
-
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
|
60
|
-
|
61
|
-
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
|
62
|
-
|
63
|
-
#define REP(i,n) FOR(i,0,n)
|
64
|
-
|
65
|
-
#define RREP(i,n) RFOR(i,0,n)
|
66
|
-
|
67
|
-
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
|
68
|
-
|
69
|
-
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
|
70
|
-
|
71
|
-
#define debug(x) cout << #x << " = " << (x) << endl;
|
72
|
-
|
73
|
-
typedef long long ll;
|
74
|
-
|
75
|
-
typedef pair<ll,ll> P;
|
76
|
-
|
77
|
-
typedef vector<vector<P>> Graph;
|
78
|
-
|
79
45
|
|
80
46
|
|
81
47
|
int root(vector<int>& tree, vector<int>& child, int i){
|
82
48
|
|
83
49
|
if(i == tree[i]){
|
84
50
|
|
85
|
-
|
51
|
+
for(int j = 0; j < child.size(); j++){
|
86
52
|
|
87
53
|
tree[child[j]] = i;
|
88
54
|
|
@@ -142,11 +108,11 @@
|
|
142
108
|
|
143
109
|
vector<int> tree1(n),child1;
|
144
110
|
|
145
|
-
|
111
|
+
for(int i = 0, i < n; i++) tree1[i] = i; // 初期化
|
146
112
|
|
147
113
|
|
148
114
|
|
149
|
-
|
115
|
+
for(int i = 0; i < k; i++){
|
150
116
|
|
151
117
|
int x,y;
|
152
118
|
|
@@ -158,7 +124,7 @@
|
|
158
124
|
|
159
125
|
|
160
126
|
|
161
|
-
|
127
|
+
for(int i = 0; i < n; i++) cout << tree[i] << " ";
|
162
128
|
|
163
129
|
|
164
130
|
|
1
想定される入力と実行例を追記しました
test
CHANGED
File without changes
|
test
CHANGED
@@ -11,6 +11,26 @@
|
|
11
11
|
|
12
12
|
|
13
13
|
UnionFindの実行後のtree1の値は任意の連結頂点間で等しい値であり、任意の非連結頂点間で異なる値になるはずなのですが、初期化したtree1[i] = iの値のままでした。
|
14
|
+
|
15
|
+
|
16
|
+
|
17
|
+
### 想定される実行結果
|
18
|
+
|
19
|
+
入力
|
20
|
+
|
21
|
+
5 3
|
22
|
+
|
23
|
+
0 2
|
24
|
+
|
25
|
+
1 4
|
26
|
+
|
27
|
+
2 4
|
28
|
+
|
29
|
+
|
30
|
+
|
31
|
+
出力
|
32
|
+
|
33
|
+
0 0 0 3 0
|
14
34
|
|
15
35
|
|
16
36
|
|
@@ -138,6 +158,10 @@
|
|
138
158
|
|
139
159
|
|
140
160
|
|
161
|
+
REP(i,n) cout << tree[i] << " ";
|
162
|
+
|
163
|
+
|
164
|
+
|
141
165
|
}
|
142
166
|
|
143
167
|
```
|