[ABC235] E - MST + 1

[Q] https://atcoder.jp/contests/abc235/tasks/abc235_e

・「最小全域木」とあるのでクラスカル法をエスパー。
Q. クラスカル法？
A. コストが低い辺から順にUniteする、ただのUnionFind。

・与えられたMで最初に木を作ってしまったら、Qの比較をどうしよう？
1. QとMが同じ辺ならcost比較できるけど、
2. 新たな辺Qを採用する場合、木の周辺構造が影響しそう。「組み換え」考慮するのきつそう。
[tips] 辺Qについている頂点ABから生えている辺を全部みる、などする「HL分解」ACルートがある。

でも、今回はクラスカルで実装。
1. 木を作ってしまうと、Ｑ判定が難しくなってしまう。
2. クエリも含めて、Ｍ＋Ｑまるっと全部クラスカル法してしまえばよさそう。
3. Mの辺が来たらUniteするし、Ｑの辺が来たらYesにすればいい。

Q. コストでソートしたいけど、4要素をもつ配列？
A. tuple<int, int, int, int> // cost, A, B, id
tupleの超簡単な使い方

 ll N;
 cin >> N;

 // 値の代入
 vector<tuple<ll, ll, ll, ll>> T(N);
 rep(i, N){
   ll x, y, z;
   cin >> x >> y >> z;
   T[i] = {x, y, z, i};
 }
 
 // 値の取り出し
 rep(i, N){
   auto&[a, b, c, d] = T[i];
   cout << a << " " << b << " " << c << " " << d << endl;
 }

実装

ll N, M, Q;
bool ans[200020];

int main(){
 cincout();
 
 cin >> N >> M >> Q;
 G.assign(N+1, vector<ll>());
 seen.assign(N+1, false);  
 UnionFind tree(N);
 
 // tuple<ll, ll, ll, ll> を入れる
 vector<tll> T;
 rep(i, M){
   ll a, b, c;
   cin >> a >> b >> c;
   --a, --b;
   T.push_back({c, a, b, -1}); // cost, a, b, id どうせ結合するからidいらない
 }
 
 rep(i, Q){
   ll u, v, w;
   cin >> u >> v >> w;
   --u, --v;
   T.push_back({w, u, v, i}); // cost, u, v, id
 }

 // solve
 sort(all(T));
 rep(i, M+Q){
   auto&[c, a, b, d] = T[i];
   // もう同じ集合に属するなら採用しない
   if (tree.issame(a, b)) continue;
   // Q
   if (d != -1){
     ans[d] = true;
   }
   // M
   else{
     tree.unite(a, b);
   }
 }
 rep(i, Q){
   if (ans[i]) cout << "Yes" << endl;
   else cout << "No" << endl;
 }
}

https://atcoder.jp/contests/abc235/submissions/28548433