fork download
copy 
  1. #include<bits/stdc++.h>
  2. typedef long long ll;
  3. #define nl "\n"
  4. #define pb push_back
  5. using namespace std;
  6.  
  7.  
  8. int k,t,x,y,tim;
  9. vector< vector<int> > v;
  10. vector<bool> vis;
  11. vector<int> out;
  12.  
  13. void dfs(int node){
  14. 	vis[node]=true;
  15. 	for(int j=0; j<k; j++)
  16. 	{
  17. 		if(v[node][j]==1 && !vis[j])
  18. 			dfs(j); 
  19. 	}
  20.  
  21. 	out[node]=tim++;
  22. }
  23.  
  24. bool isDag(){
  25. 	tim=0;
  26. 	fill(vis.begin(), vis.end(), false);
  27.  
  28. 	for(int i=0; i<k; i++){
  29. 		if(!vis[i]){
  30. 			dfs(i);
  31. 		}
  32. 	}	
  33. 	for(int i=0; i<k; i++)
  34. 	{
  35. 		for(int j=0; j<k; j++){
  36. 			if(v[i][j]==1 && out[j]>=out[i])
  37. 				return false;
  38. 		}
  39. 	}
  40. 	return true;
  41. }
  42.  
  43.  
  44. void solve()
  45. {
  46. 	cin>>k>>t;
  47. 	v.resize(k);
  48. 	vis.resize(k);
  49. 	out.resize(k);
  50. 	for(int i=0; i<k; i++)
  51. 	{
  52. 		v[i].resize(k);
  53. 		fill(v[i].begin(),v[i].end(),0);
  54. 	}
  55.  
  56. 	for(int idx=1; idx<=t; idx++){
  57. 		cin>>x>>y;
  58. 		x--; y--;
  59. 		v[x][y]=1;
  60. 		if(!isDag()){
  61. 			v[x][y]=0;
  62. 			cout<<x+1<<" "<<y+1<<"\n";
  63. 		}		
  64. 	}	
  65. 	cout<<0<<" "<<0<<"\n";
  66. }
  67. int main()
  68. {
  69.  
  70.         solve();
  71.   return 0;
  72. }
  73.  
Success #stdin #stdout 0s 4492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/KkUat6
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!