Hi , I am also getting WA with my code for PARADOX problem .
My code logic is :
I pick up an unvisited statement , assume it true and then keep iterating till I get a loop . If the statement at which a loop is formed is contradicted , then I assume a paradox. For completion I again find a unvisited statement, set all the assumptions back to false and again start my algo . My code, along with appropriate comments is :
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<set>
#include<stdlib.h>
#include<utility>
using namespace std;
int main()
{
int i,n,j,count;
char val[10];
bool paradox , predictval;
scanf("%d",&n);
while(n != 0)
{
/*start initialization*/
/*declaring vectors instance- to store input
visited - to keep track of visited sentences
record - record of what val the sentence if acc to prev computation
*/
vector< pair<int,bool> > instance(n+1);
vector<bool> record(n+1,false),visited(n+1,false);
vector<bool> visited1(n+1,false);
for(i=1;i<=n;i++)
{
scanf("%d",&instance[i].first);
scanf("%s",val);
if( strcmp(val,"true") == 0 )
instance[i].second=true;
//printf("true \n");
else
instance[i].second=false;
//printf("false \n")
}
/*initialization complete */
paradox=false;
for(i=1;i<=n;i++)
/* this loop is to keep track of how many set of disjoint sentences are there. we come out of this loop when all ver
tices have been visited */
{
if(visited1[i] == true ) continue;
record[i]=true;
// store current state before exploring
for(j=1;j<=n;j++)
{ visited[j]=false; record[j]=false; }
while(true) /* we come out of this loop if contradiction i.e paradox */
{
visited[i]=true;
visited1[i]=true;
predictval = !( instance[i].second ^ record[i] );
/* value the next sentence should actually have. determined by value the curr sentence
wants plus the value of current sentece itself */
if(visited[instance[i].first] == true)/*check if we have visited this node before*/
{
if(predictval != record[instance[i].first])/*check if contradiction */
{
//printf("paradox found here\n");
paradox=true; goto hell;
}
else
break; /* if no contradiction then go back and pick another set of unexplored sentences */
}
else /* we are visiting this sentence for the first time */
{
i=instance[i].first;/* this is the new i */
record[i]=predictval;
}
} //while(true) loop ends
} //for loop ends
hell:
if(paradox == true)
printf("PARADOX\n");
else
printf("NOT PARADOX\n");
scanf("%d",&n);
}//while n!=0 loop ends
return 0;
}