#include "collapse.h"
#include <vector>
#include <set>
using namespace std;
const int MAXN = 1e5;
static int PP[MAXN][4];
int getp(int x)
{
if (PP[x][0] == x)
return x;
return (PP[x][0] = getp(PP[x][0]));
}
void join(int a, int b)
{
a = getp(a);
b = getp(b);
if (a == b)
return;
if (PP[a][1] < PP[b][1])
swap(a, b);
PP[b][0] = a;
PP[a][1] += PP[b][1];
}
vector<int> simulateCollapse(
int N,
vector<int> T,
vector<int> X,
vector<int> Y,
vector<int> W,
vector<int> P)
{
for (int i = 0; i < X.size(); ++i)
if (X[i] > Y[i])
swap(X[i], Y[i]);
vector<int> ans(W.size());
vector<pair<int,int>> Q(W.size());
for (int i = 0; i < W.size(); ++i)
Q[i] = pair<int,int>(W[i], i);
for (int z = 0; z < W.size(); ++z)
{
for (int j = 0; j < N; ++j)
{
PP[j][0] = j;
PP[j][1] = 1;
PP[j][2] = 0;
}
int i = Q[z].second;
int cut = P[i];
//printf("$%d %d$\n", i, cut);
set<pair<int,int>> edges;
for (int j = 0; j <= W[i]; ++j)
{
//printf("|%d %d %d|\n", T[j], X[j], Y[j]);
if (T[j] == 0)
edges.insert(pair<int,int>(X[j], Y[j]));
else
edges.erase(pair<int,int>(X[j], Y[j]));
}
set<pair<int,int>>::iterator f;
for (f = edges.begin(); f != edges.end(); ++f)
{
//printf("((%d %d))\n", f->first, f->second);
if (f->first > cut || f->second <= cut)
{
join(f->first, f->second);
//printf("(%d %d)", f->first, f->second);
}
}
int res = 0;
for (int j = 0; j < N; ++j)
{
int a = getp(j);
if (PP[a][2] == 0)
{
PP[a][2] = 1;
//printf("!%d!",a);
++res;
}
}
//printf("=(%d)%d\n", i,res);
ans[i] = res;
}
return ans;
}
