fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define s(a) scanf("%d", &a)
  4. #define ss(s) scanf("%s", s)
  5. #define pb(a) push_back(a)
  6. #define mk(a,b) make_pair(a,b)
  7.  
  8. int color[100] ;
  9. //same is used to store all the element which belong to same set 
  10. vector<int> same[105] ;
  11. //diff is used to store all element which must belong different set
  12. vector<pair<int,int>> diff;
  13.  
  14. //normal dfs
  15. void dfs( int v , int col , int par )
  16. {
  17. 	color[v] = col;
  18. 	for( auto u : same[v] )
  19. 	{ 
  20. 		if( u != par )
  21. 		    dfs( u , col , v);
  22. 	}
  23. }
  24.  
  25.  
  26. int main() {
  27.  
  28.    int n , a;
  29.    s(n);
  30.    while( n!= 0 )
  31.    {
  32.    	int j = 0;
  33.    	//clearing data
  34.    	for( int i = 1 ; i <= n ; i++ )
  35.    	{
  36.    		same[i].clear();
  37.    		color[i] = -1;
  38.    	}
  39.    	diff.clear();
  40.  
  41.    	char s[10];
  42.    	int flag = 0;
  43.    	for( int i = 1 ; i <= n ; i++ )
  44.    	{
  45.    		s(a);
  46.    		ss(s);
  47.  
  48.  
  49.    		if( s[0] == 'f' )
  50.    		{
  51.    			//if string is false then statements belong to different set i.e, one can
  52.    		   //be true and other can be false or vice-versa
  53.    			diff.push_back(mk(i,a));
  54.    			j++;
  55.    		}
  56.    		else
  57.    		{
  58.    			//if string is true then either both are true or false i.e, they belong
  59.    			//to same set 
  60.    			same[i].pb(a);
  61.    			same[a].pb(i);
  62.    		}
  63.    	}
  64.  
  65.       //flag is 1 if there is paradox and 0 if there is no paradox
  66.       // a paradox is encountered if two elements of same sets are said to be false
  67.    	for( int i = 0 ; i < j ; i++ )
  68.    	{
  69.    		int a = diff[i].first , b = diff[i].second;
  70.  
  71.  
  72.    		if( color[a] == -1 && color[b] == -1 )
  73.    		{
  74.    			// if both are uncolored then color one and if other one is colored 
  75.    			// then we know a and b belonged to same set , so it is a paradox
  76.  
  77.    			dfs(a,0,0);
  78.    			if( color[a] == color[b] )
  79.    			{ 
  80.    				flag = 1;
  81.    				break;
  82.    			}
  83.    			dfs(b,1,0);
  84.    		}
  85.    		else if( color[a] != -1 && color[b] == -1 )
  86.    		{
  87.    			//one colored and other uncolored
  88.    			dfs(b,1-color[a],0);
  89.    			if( color[a] == color[b] )
  90.    			{
  91.    			    	flag = 1;
  92.    			   	break;
  93.    			}
  94.  
  95.    		}
  96.    		else if( color[a] == -1 && color[b] != -1 )
  97.    		{
  98.    			dfs(a , 1-color[b],0);
  99.    			if( color[a] == color[b] )
  100.    			{
  101.  
  102.    					flag = 1;
  103.    					break;
  104.  
  105.    			}
  106.    		}
  107.    		else if( color[a] == color[b] )
  108.    		{
  109.    			// if both are colored by the same color 
  110.    			dfs( a ,1-color[a] ,0);
  111.    			if( color[a] == color[b] )
  112.    			{
  113.    				flag = 1;
  114.    				break;
  115.    			}
  116.    		}
  117.  
  118.    	}
  119.  
  120.    	if( flag )
  121.    	{
  122.    		cout << "PARADOX\n";
  123.    	}
  124.    	else
  125.    	{
  126.    		cout << "NOT PARADOX\n";
  127.    	}
  128.    	s(n);
  129.    }
  130.  
  131.  
  132.  
  133. 	return 0;
  134. }
Success #stdin #stdout 0s 4472KB
comments (?)
stdin 
4
3 false
4 false
4 false
3 false
0
stdout 
NOT PARADOX
https://ideone.com/HCpQV1
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!