#include "game.h"
#include <bits/stdc++.h>
using namespace std;
/* The ideal strategy is to keep saying no unless it is the last
edge such that if we say no, then the graph becomes disconnected.
Assume that the graph is partially filled, such that there are two
components now. How to check if the guessed edge is the last edge?
The number of possible edges between the two components are
sizeA * sizeB. If cur_edge == sizeA * sizeB, then we can add an edge.
Observe that the optimal strategy for the asker is to ask questions
on two disjoint vertices. All already connected vertices are meaningless.
By denying edges, we ensure that the asker would need all Q = N * (N - 1) / 2
questions.
Proof: assume that there are n disjoint components. Let A, B, C, D be sets
with sizeA <= sizeB <= sizeC <= sizeD. What is the optimal strategy of
minimum questions needed? There are a few cases:
1. sizeA * sizeB + sizeC * sizeD + (sizeA + sizeB) * (sizeC + sizeD) total questions.
= sizeA * sizeB + sizeA * sizeC + sizeA * sizeD + sizeB * sizeC + sizeB * sizeD
+ sizeC * sizeD
2. sizeA * sizeB + (sizeA + sizeB) * sizeC + (sizeA + sizeB + sizeC) * sizeD
= sizeA * sizeB + sizeA * sizeC + sizeA * sizeD + sizeB * sizeC + sizeB * sizeD
+ sizeC * sizeD
for any permutation of A, B, C, and D. Thus we can see that for any strategy, if we
give the asker an edge at the last possible edge between two currently disjoint
components, then asker would require the same number of questions.
The total questions needed is: 1 * 1 + 2 * 1 + 3 * 1 + ... = N * (N - 1) / 2.
So the strategy of waiting until last edge of two currently disjoint components is an
optimal strategy.
We can keep track of components' size with disjoint set data structure and countEdges
with adjacency matrix.
*/
struct Disj {
vector<int> p, sz;
void init(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
sz.assign(n, 1);
}
int par(int n) {
return p[n] == n ? n : p[n] = par(p[n]);
}
bool join(int a, int b) {
a = par(a), b = par(b);
if (a == b) return false;
p[a] = b;
sz[b] += sz[a];
sz[a] = 0;
return true;
}
};
int N;
vector<vector<int>> cnt;
Disj dsu;
void initialize(int n) {
N = n;
cnt.assign(n, vector<int>(n, 0));
dsu.init(n);
}
int hasEdge(int u, int v) {
u = dsu.par(u), v = dsu.par(v);
if (u > v) swap(u, v);
if (++cnt[u][v] == dsu.sz[u] * dsu.sz[v]) {
dsu.join(u, v);
for (int i = 0; i < N; i++) cnt[min(v, i)][max(v, i)] += cnt[min(u, i)][max(u, i)];
return 1;
} else {
return 0;
}
}
