Used union-rank algorithm to get the output.Not sure wjetjer the approach is the right one. Please check https://ide.codingblocks.com/s/184260.
XYZ Encryption in Graph
First observation is that, if two nodes, u and v are not connected, then one of them is āxā and
another one is āzā. Second observation is that if $S_1$ is a set of nodes with value āxā, and set
$S_2$ is a set of nodes with value āzā, then interchanging them will not change the encrypted
graph, i.e. assign value āzā to set $S_1$ and value āxā to set $S_2$. So first we will search for a
pair of nodes, u and v , which are not connected, assign one of them to āxā and another to āzā.
Now for the rest of the nodes, if a node, w is connected to both u and v , assign value āyā to it. If
a node, w is connected to node u only, then assign value āxā to it. If a node, w is connected to
node v only, then assign value āzā to it. Now since you have assigned values to all of the nodes,
for every pair of nodes, check whether it satisfies the rules of encryption. If it does not, then
answer is NO.
@chhavibansal , can it not be possible that there exist a another arrangement of x , y, z that will give us YES.
PLEASE REPLY
what other combination do u think can be feasible?
please state example
yes you are right.
thanks .
1 Like