# How to solve CHAIN - Strange Food Chain spoj question.

Check here

Solution
``````#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

struct DSU {
int n;
std::vector<int> root;
std::vector<int> d;

explicit DSU(int _n) : n(_n) {
root.resize(n);
d.resize(n);
for (int i = 0; i < n; ++i) {
root[i] = i;
d[i] = 0;
}
}

int Find(int x) {
if (x == root[x]) return x;
int par = root[x];
root[x] = Find(root[x]);
d[x] += d[par];
return root[par];
}

bool Unite(int x, int y, int type) {
if (x >= n || y >= n) return true;
int px = Find(x);
int py = Find(y);
int val = ((d[x] - d[y] - type) % 3 + 3) % 3;
if (px == py) {
return val != 0;
} else {
root[px] = py;
d[px] = 3 - val;
return false;
}
}
};

class StrangeFoodChain {
public:

void solve(std::istream& cin, std::ostream& cout) {
int _t = 1;
cin >> _t;
for (int _tc = 1; _tc <= _t; ++_tc) {
int n, k;
cin >> n >> k;
DSU dsu(n);
int ans = 0;
for (int i = 0; i < k; ++i) {
int type, x, y;
cin >> type >> x >> y;
x--, y--, type--;
ans += dsu.Unite(x, y, type);
}
cout << ans << '\n';
}
}
};

int32_t main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
StrangeFoodChain solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
``````
1 Like

Can you please explainâ€¦Logic begind vector d;