@@ -0,0 +1,2597 @@
+// Author: Param Singh %3Cparamsingh258@gmail.com%3E%0A// PARADOX: http://www.spoj.com/problems/PARADOX/%0A%0Aimport java.io.*;%0Aimport java.util.*;%0A%0Aclass Paradox %7B%0A    private class Node %7B%0A        int val;%0A        int inval;%0A        int index;%0A        List%3CNode%3E t;%0A        int num;%0A        List%3CNode%3E f;%0A        Node(int i) %7B%0A            val = -1;%0A            inval = -1;%0A            index = i;%0A            t = new ArrayList%3CNode%3E();%0A            f = new ArrayList%3CNode%3E();%0A            num = 0;%0A        %7D%0A%0A        void add_true(Node x) %7B%0A            t.add(x);%0A            num++;%0A        %7D%0A%0A        void add_false(Node x) %7B%0A            f.add(x);%0A            num++;%0A        %7D%0A    %7D%0A%0A    Node nodes%5B%5D;%0A    Paradox(int n) %7B%0A        nodes = new Node%5Bn%5D;%0A        for (int i = 0; i %3C n; i++)%0A            nodes%5Bi%5D = new Node(i);%0A    %7D%0A%0A    boolean dfs(Node x, int expected, boolean first) %7B%0A        if (x.val == -1 %7C%7C first)%0A            x.val = expected;%0A        else %7B%0A            return (x.val != expected);%0A        %7D%0A        int nexp;%0A        for (Node node: x.t) %7B%0A            nexp = x.val;%0A            if (dfs(node, nexp, false))%0A                return true;%0A        %7D%0A        for (Node node: x.f) %7B%0A            nexp = 1 - x.val;%0A            if (dfs(node, nexp, false))%0A                return true;%0A        %7D%0A        return false;%0A    %7D%0A%0A%0A    boolean isParadox() %7B%0A        for (Node n: nodes) %7B%0A            if (n.val == -1 && n.num != 1) %7B%0A                boolean x = dfs(n, 1, true);%0A                boolean y = dfs(n, 0, true);%0A                if (!x && !y)%0A                    dfs(n, 1, true);%0A                else if (!x)%0A                    dfs(n, 1, true);%0A                else if (!y)%0A                    dfs(n, 0, true);%0A                else%0A                    return true;%0A            %7D%0A        %7D%0A        return false;%0A    %7D%0A%0A    void add(int i, int n, boolean x) %7B%0A        if (x) %7B%0A            nodes%5Bi%5D.add_true(nodes%5Bn%5D);%0A        %7D%0A        else %7B%0A            nodes%5Bi%5D.add_false(nodes%5Bn%5D);%0A        %7D%0A        nodes%5Bn%5D.num++;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Scanner in = new Scanner(System.in);%0A        int n = in.nextInt();%0A        while (n != 0) %7B%0A            Paradox p = new Paradox(n);%0A            for (int i = 0; i %3C n; i++) %7B%0A                int dest = in.nextInt();%0A                boolean x = in.next().equals(%22true%22);%0A                p.add(i, dest-1, x);%0A            %7D%0A            if (p.isParadox())%0A                System.out.println(%22PARADOX%22);%0A            else%0A                System.out.println(%22NOT PARADOX%22);%0A            n = in.nextInt();%0A        %7D%0A    %7D%0A%7D%0A

Work on PARADOX (SPOJ)