Problem link
Solution LINK
I have used union find. I got wrong answer in two case, i dont know what wrong I am doing.Please help
I can’t say where you are going wrong but I can suggest you another way to approach this question. The idea is to store all the relations which have ‘!’ sign in another vector and check them afterwards. We first make a graph showing the only ‘=’ relations. Then we run dfs on the entire graph and group all the nodes belonging to the same component as one. For this, we maintain the component array.
Now, after we have completed the dfs we check for all the inequalities stored in our vector. If the component number of the nodes are same then the relationship is not feasible and we simply break. If we find no such relationship then we can print “YES”.
I am also attaching the code for your reference.
thnks bro… i got the error also with ur comment. lets say 1=2 , 2!=3, 3=1 in my case it will print yes since i have checked the ! statement before = … thnx a lot…
I have tried this questions using the concept of DFS and connected components and got AC.
thnx… for the approach…