# Calculating pre-xors in a Tree (DSU application)

Created @Nov 28, 2020 12:22 PM

This is related to a problem I came across in OJ 4 (DSA) and the following is the solution:

``````int n, m, k;
map<int, int> parent, val;
int net = 0, ans = INF;

int power(int x, int N)
{
int y = 1;
while (N > 0)
{
if (N & 1)
y = (y * x) % MOD;
N /= 2;
x = (x * x) % MOD;
}

return y;
}

int Get(int i)
{
if (!parent.count(i)) parent[i] = i, val[i] = 0;
return parent[i];
}

int Find(int x)
{
int p = Get(x);
if (p == x) return x;

int r = (parent[x] = Find(p));
val[x] ^= val[p];
return r;
}

void Union(int i, int j, int x)
{
int a = Find(i), b = Find(j);
x ^= val[i] ^ val[j];

if (a != b)
{
parent[a] = b;
val[a] = x;

net--;

} else
{
if (x == 0) return;
else
ans = 0;
}
}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cin >> n >> m >> k;
net = n + m - 1;

while (k--)
{
int i, j, x;
cin >> i >> j >> x;
j = 1005 + j;

if (ans != 0)
Union(i, j, x);
}

if (ans == 0)
cout << 0 << endl;
else
{
ans = power(2, 30);
ans = power(ans, net);
cout << ans << endl;
}
return 0;
}``````