DSU #1 Dish Owner CodeChef

Dish Owner Problem Code: DISHOWN

Problem Statement: here

Solution: This is the first problem in the Disjoint Set Union series, so bare a small lecture from my side. Disjoint Set Union is a technique that allows us to deal with disjoint sets. We can solve problems involving disjoint sets. The two important functions of this data structure is:

1. Find(x) -> It will find the root node of my current component/set.
2. Union(x,y) -> It is used for uniting two disjoint sets. We can assign the root node of one set the parent of another, depending on SOME rules. Sometimes, it depends on the height of the subtree or rank or number of nodes in set or any other rule.

The code snippet uses the rank and path compression technique for DSU.

// DSU starts here.................. struct subset { ll parent; ll rank; }; ll find(struct subset subsets[], ll i) { // find root and make root as parent of i (path compression) if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } void Union(subset subsets[], ll x, ll y) { ll xroot = find(subsets, x); ll yroot = find(subsets, y); // Attach smaller rank tree under root of high rank tree // (Union by Rank) if (subsets[xroot].rank < subsets[yroot].rank) subsets[xroot].parent = yroot; else if (subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot; // If ranks are same, then make one as root and increment // its rank by one else { subsets[yroot].parent = xroot; subsets[xroot].rank++; } } //DSU ends here....................

The Approach for question: 

Initially, we can set the parent of ith dish the ith index itself, because ith chef owns it.

Then important observation is:

1. The root dish for ith chef is now set as the initial dish he had.
2. The important thing to note is, every chef will come forward with the dish of maximal score to fight and that dish is nothing but the initial dish only. Because if his initial dish is bigger than other dishes of other chefs, he is getting all of their dishes, but all dishes of other chefs are already smaller than his initial dish, otherwise another chef would have won. So, when we find the root of any disjoint set, we can check for the score on that dish and figure out which chef will win and assign accordingly.

The Code:

struct subset { ll parent; ll rank; }; ll find(struct subset subsets[], ll i) { // find root and make root as the parent of i (path compression) if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } void solve() { ll n; cin >> n; ll a[n+1]; rep(i,1,n+1) cin >> a[i]; subset myset[n+1]; rep(i,1,n+1){ myset[i].parent = i; myset[i].rank = 0; } ll m; cin >> m; rep(i,0,m){ ll r; cin >> r; if (r == 0){ ll x,y; cin >> x >> y; ll xroot = find(myset,x); ll yroot = find(myset,y); if(xroot == yroot) { cout<<"Invalid query!"<<endl; } if (a[xroot] < a[yroot]){ myset[xroot].parent = yroot; } else if (a[xroot] > a[yroot]){ myset[yroot].parent = xroot; } } else{ ll x; cin >> x; cout << find(myset,x) << endl; } } }