How to solve CHAIN - Strange Food Chain spoj question.

general
1
2

Check here

3
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
4

Can you please explain…Logic begind vector d;

1 Like