Link : PARADOX
Category : Graphs
Hint : constructed an appropriate graph and do a depth-first traversal.
Solution : Consider this as a directed graph, with edge from vertex A to vertex B if statement A tells about statement B. Make list of incoming and outgoing edges for each vertex, and then do simple depth-first traversal on both, incoming and outgoing edges. If a statement claims opposite of the truth value assigned to an already visited node, then there is a paradox.
Note that for the traversal, the starting vertex can be anyone, and its truth value can be anything (true or false, because if truth value of one statement is changed, then truth value of all nodes reachable by it via directed/directing edges also gets flipped, hence preserving the PARADOX or NOT PARADOX answer.
Code:
Category : Graphs
Hint : constructed an appropriate graph and do a depth-first traversal.
Solution : Consider this as a directed graph, with edge from vertex A to vertex B if statement A tells about statement B. Make list of incoming and outgoing edges for each vertex, and then do simple depth-first traversal on both, incoming and outgoing edges. If a statement claims opposite of the truth value assigned to an already visited node, then there is a paradox.
Note that for the traversal, the starting vertex can be anyone, and its truth value can be anything (true or false, because if truth value of one statement is changed, then truth value of all nodes reachable by it via directed/directing edges also gets flipped, hence preserving the PARADOX or NOT PARADOX answer.
Code:
what this line "bool imp=not(state[curr] xor claims[curr]);" is doing?? please explain....
ReplyDeleteAnswered below
Deletebool imp=not(state[curr] xor claims[curr]);
ReplyDeleteCan you explain this ?
xor means either state[curr] is true or claims[curr] is true, not of that would mean both should be true or both should be false.
DeleteThus the variable imp would get the implied value (would be true if "curr" says it is true and "curr" itself is true, or if "curr" says it is false and "curr" itself is false