fork download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<string>
  6. #include<limits>
  7. #include<queue>
  8. using namespace std;
  9. #define MS 1005
  10. #define identity 0
  11. #define ll long long
  12. #define MOD 1000000000
  13. #define dd float 
  14. #include<iomanip>
  15. #include<list>
  16.  
  17.  
  18. int a[MS][MS];//matrix that takes input 
  19.  
  20. bool visited[MS];//marks visited elements 
  21.  
  22.  struct node //stores information about the node 
  23.  {   int index;
  24.      int value;
  25.       int pos;
  26.   node()
  27.   {
  28.   	value=2;
  29.   }
  30.  }b[MS];
  31.  
  32.  
  33.  
  34.  class Graph
  35. {
  36.     int V;    
  37.     list<int> *adj;  
  38. public:
  39.     Graph(int V);  
  40.     void addEdge(int v, int w); 
  41.     void bfs(int);
  42. };
  43. Graph::Graph(int V)
  44. {
  45.     this->V = V;
  46.     adj = new list<int>[V];//stores adjacent element 
  47. }
  48.  
  49. void Graph::addEdge(int v, int w)
  50. {
  51.     adj[v].push_back(w); //for adding edge in graph 
  52. }
  53.  
  54.  
  55.  struct loop
  56.   {
  57.   	int sum0;//stores count of 1(lower number)
  58.   	int  sum1;//stores count of 0(higher numvber)
  59.   	int diff;//stores absolute diff
  60.   	int rev;//stores value for reversal of values in that index 
  61.   	loop()
  62.   	{
  63.   		rev=0;
  64. 	  }
  65.   }x[MS];
  66.  
  67.  
  68. int y[MS];
  69. int flag2=1,cnt[2];//flag to store if traversal if the initial condition has a solution or not 
  70. //cnt to store count of 0 and 1 for that index 
  71.  
  72.  
  73.  
  74. //push in queue to add node to the queue
  75. void push_in_queue(queue<int> &s,int  top,int index,int val)
  76. { 
  77. 	b[top].value=1-val;
  78. 	b[top].index=index;
  79. 	cnt[1-val]++;
  80.  
  81. 	s.push(top);
  82.  
  83. 	visited[top]=true;
  84. }
  85.  
  86.  
  87.  //bfs to traverse through graph 
  88. void Graph::bfs(int  start)
  89. {
  90.  
  91.  
  92. 	queue<int> s;
  93. 	s.push(start);
  94. 	visited[start]=true;
  95.  
  96. 	while(s.empty()==false)
  97. 	{
  98. 		int top=s.front();
  99. 		s.pop();
  100.  
  101. 		   list<int>::iterator i;
  102. 		    for(i = adj[top].begin(); i != adj[top].end(); ++i)
  103.         {
  104.             if(visited[*i]==true)
  105.             {  
  106.                if(b[*i].value==b[top].value)
  107.                { flag2=0;
  108.                	 return;
  109.  
  110. 			   }
  111.             }
  112.             else
  113.              {
  114.              	push_in_queue(s,*i,b[top].index,b[top].value);
  115. 			 }
  116.         }
  117.  
  118.     }
  119.  
  120. 	return ;
  121. }
  122.  
  123. int main()
  124. {
  125. 	int t;
  126. 	cin>>t;
  127. 	while(t--)
  128. 	{
  129. 		int n;cin>>n;
  130. 		  for(int i=0;i<n;i++)
  131. 		  {
  132. 		  	for(int j=0;j<n;j++)cin>>a[i][j];
  133. 		  }
  134.  
  135. 		  int flag=1;
  136.  
  137. 		  for(int i=0;i<n;i++)
  138. 		  {
  139. 		  	if(a[i][i]==1)flag=0;
  140. 		  }
  141. 		  // flag to check if any diagonal element has an entry 1 or not 
  142.  
  143. 	if(flag==1)
  144. 	  {  
  145. 		     flag2=1;
  146. 		    int idx=0;
  147. 		    Graph g(n);
  148.  
  149. 		    for(int i=0;i<n;i++)
  150. 		    {   
  151. 		    	for(int j=i+1;j<n;j++)
  152. 		    	{
  153. 		    		if(a[i][j]==1)
  154. 		    		{
  155. 		    			g.addEdge(i,j);
  156. 		    			g.addEdge(j,i);
  157.  
  158. 					}
  159.  
  160. 				}
  161. 			}
  162.  
  163.  
  164. 		   idx=0;
  165. 		   //initializing different values with 0 values 
  166. 		   for(int i=0;i<n;i++)
  167. 		   {
  168. 		   	b[i].value=2;x[i].rev=0; visited[i]=false; b[i].pos=i;  x[i].sum0=0; x[i].sum1=0; x[i].rev=0; x[i].diff=0;
  169. 		   }
  170.  
  171. 		    for(int i=0;i<n;i++)
  172. 		    { 
  173. 		    	  if(!visited[i])
  174. 		            	{  
  175. 		    	     // if not visited , update index value and perform bfs and mark the nodes with their values 
  176. 		 	    	       {	idx++;
  177. 		    		            b[i].value=1;
  178. 		    		            b[i].index=idx;
  179. 		    		            cnt[1]=1;cnt[0]=0;
  180. 		    		            g.bfs(i); 
  181.  
  182. 		    		            if(cnt[1]>cnt[0])
  183. 					                 {
  184. 						                  x[idx].sum0=cnt[0];
  185. 						                  x[idx].sum1=cnt[1];
  186. 					                      x[idx].diff=cnt[1]-cnt[0];
  187. 					                      x[idx].rev=1;
  188. 					                  }
  189. 					             else
  190. 					                  {
  191. 						                x[idx].sum0=cnt[1];
  192. 					                 	x[idx].sum1=cnt[0];
  193. 						                x[idx].diff=cnt[0]-cnt[1];
  194. 					                    x[idx].rev=0;						
  195. 					                  }		    		
  196.  
  197. 				            }
  198. 		                }
  199. 		    }
  200.  
  201.  
  202. 		  //y to store  the the index of difference value that added upto make the value 
  203. 		     for(int i=0;i<=n;i++)
  204. 		     {
  205. 		     	y[i]=0;
  206. 			 }
  207. 			  y[0]=1;
  208.  
  209.  
  210. 			 //forming the array y[] 
  211. 			  for(int i=1;i<=idx;i++)
  212. 			  {   if(x[i].diff>0)
  213. 			      {
  214.  
  215. 			       for(int j=n;j>=x[i].diff;j--)
  216. 			           { 
  217. 					        if(y[j-x[i].diff]!=0)
  218. 			                     {  if(y[j]==0)
  219. 			  	                        y[j]=i;
  220. 			                      } 			
  221. 			           }
  222. 			      }
  223. 			  } 
  224.  
  225.  
  226.  
  227. 			  int flag3=1,track=0,sum=0;	 				 
  228. 				//sum stores the minimum sum
  229. 			   for(int i=1;i<=idx;i++)
  230. 			      {
  231. 			  	        sum=sum+x[i].sum0;
  232. 			      }
  233.  
  234. 			   int temp=0;
  235. 			   //temp stores the maximum product of (number of 0s and number of 1s)
  236. 			   int rem= (sum*(n-sum));
  237. 			   if(rem>temp)
  238. 			   {
  239. 			   	temp=rem;track=0;
  240. 			   }
  241. 			  for(int i=1;i<=(n-2*sum);i++)
  242. 			       {  
  243. 				    if(y[i]!=0)
  244. 					{
  245. 						int rem= (sum+i)*(n-sum-i);
  246. 						if(rem>temp)
  247. 						   {track=i; temp=rem; }    	
  248. 			        }		  	        
  249.  
  250. 			       }
  251.  
  252.  
  253.  
  254. 			//now , updating the values of zeros , if needed
  255. 			 while(track>0)
  256. 			     {
  257. 			         	x[y[track]].rev=1-x[y[track]].rev;
  258. 			 	         track=track-x[y[track]].diff;
  259. 			     }
  260.  
  261. 			//reversing tha values of b[] for which rev is 1
  262. 			     for(int i=0;i<n;i++)
  263. 			        { 	
  264. 			          	if(x[b[i].index].rev==1)
  265. 			  	                {
  266. 			  	                  	b[i].value=1-b[i].value;
  267. 				                 }
  268. 			        }
  269.  
  270.  
  271. 				 //if the input conditoin has a solution ....print ans
  272. 				 if(flag2==1)
  273. 				     {     
  274. 				 	        for(int i=0;i<n;i++)
  275. 							 {cout<<b[i].value<<"\t";	}			 	
  276. 				 	        cout<<endl;
  277. 				     }
  278. 				 else
  279. 				     {   
  280. 				 	        cout<<"-1"<<endl;
  281. 				     }
  282.  
  283. 		}
  284. 	   else
  285. 		{
  286. 		  	cout<<"-1"<<endl;
  287. 		}
  288.  
  289. 	}
  290.  
  291. 	return 0;
  292. }
Success #stdin #stdout 0s 6800KB
comments (?)
stdin
copy 
3
4
0 0 0 1
0 0 0 1
0 0 0 0
1 1 0 0
4
1 0 0 1
0 1 0 1
0 0 0 0
1 1 0 0
2
0 0
0 0
stdout
copy 
1	1	0	0	
-1
1	0
https://ideone.com/ko3FYE
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!