PARADOX

Problem Link

#include <iostream>
#include <vector>
using namespace std;

bool isParadox;
int stmt[101]; // 0 if stmt[i] is false, 1 if true,  -1 if not yet decided
int p[101]; // store root of a component

void dfs(int s, vector<pair<int,int> > graph[], int root)
{
 
    p[s] = root;
    for(int i = 0; i < graph[s].size(); i++)
    {
        int v = graph[s][i].first;
        int c = graph[s][i].second;
        if(stmt[v] == -1)
        {
            //if stmt s is true then whatever it says about other stmt is true
            //else whatever it says is false. so we have to take its complement
            stmt[v] = stmt[s] == 1 ? c : 1 - c;
         
            dfs(v, graph, root);
        }
        else
        {
            //if a stmt is already marked as true or false
            //then we have to check whether it conficts with current marking
            int vertextColor = stmt[s] == 1 ? c : 1 - c;
            if(stmt[v] != vertextColor)
            {
                //we get conflict in marking a node as true or false
                //so it is paradox
                isParadox = true;
                return;
            }
        }
    }
}
int main()
{
    int n, s;
    string st;
    cin >> n;
    while(n)
    {
        // store stmt no and its truth value
        vector<pair<int,int> > graph[n + 1];
        isParadox = false;
        for(int i = 0; i < n + 1; i++)
        {
            stmt[i] = -1;
            p[i] = i;
        }
        for(int i = 1; i <= n; i++)
        {
            cin >> s >> st;
         
            if(st.compare("false") == 0)
            {
                graph[i].push_back(make_pair(s, 0));
            }
            else
            {
                graph[i].push_back(make_pair(s, 1));
            }
         
        }

        for(int vertex = 1; vertex <= n; vertex++)
        {
            isParadox = false;
            if(stmt[vertex] == -1)
            {
                //assume stmt is true and find truth value of other stmt
                stmt[vertex] = 1;
                dfs(vertex, graph, vertex);
            }
            if(isParadox)
            {
                //if initial assumption is not correct reset all truth values of that component
                //assume stmt is false now and find truth value of other stmt
                isParadox = false;
                for(int j = 1; j <= n; j++)
                {
                    if(p[j] == vertex)
                    {
                        stmt[j] = -1;
                    }
                }
                // assume stmt is false now
                stmt[vertex] = 0;
                dfs(vertex, graph, vertex);
            }

            //if neither of the assumption satisfies then it is a paradox
            if(isParadox)
            {
                cout << "PARADOX\n";
                break;
            }
        }

        if(!isParadox)
        {
            cout << "NOT PARADOX\n";
        }

        cin >> n;
    }
}