Devide n vertical into 2 group A and B.
There are q query of two type: 1 u v, tell you that u and v belong to different group; 2 u v, print "YES" if u and v belong to one group, "NO" if u and v not belong to one group, "NOT GIVEN" if there is not enough information about u and v, based on the information has given in query type 1;
For example:
Input: 3 5
2 1 2
1 1 2
2 1 2
1 2 3
2 1 3
Output:
NOT GIVEN
NO
YES
I have stucked in this problem for a week, please help me ToT.
Auto comment: topic has been updated by tkien1707 (previous revision, new revision, compare).
Can you just share link of the problem? I will try to solve it
Yeah, thank you so much, its a OJ in our local, hope you can access it.
https://marisaoj.com/problem/318
The only part of this problem that differs from the main DSU structure is the "NOT GIVEN" response.
For "YES" and "NO" just use a very basic DSU (or with some simple modifications, if you like), and for "NOT GIVEN" use a map/set/etc. where you will store information if any number already appeared in type 1 query, and if it's not then it's the only case when "NOT GIVEN" is a valid response (and you need to check for it BEFORE the DSU query). That's all.
Update: I checked the original problem statement, the solution I described above won't work for this (consider 1 1 2 and 1 3 4 and 2 1 4 — the response should be "NOT GIVEN" even though these numbers have already appeared). I believe that this can be solved using bipartite graph modification for the type 1 query, where if the both ingridients are unknown you create new bipartite group with them, and if one of them is known then you merge it. If in type 2 query two ingridients are from different groups then it's "NOT GIVEN", if they are from different sets the answer is "NO", otherwise "YES"
For type 1 query add an edge between 2 nodes and color them opposite color
For type 2 if nodes belong to different component we can't determine otherwise if they have same color it is safe and fatal if different color.
While merging 2 components, merge small to large