fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<map>
  4. #include<set>
  5. #include<algorithm>
  6. #include<cstdio>
  7. #include<functional>
  8. #include<cstdlib>
  9. #include<ctime>
  10. #include<cassert>
  11. #include<iomanip>
  12. #include<string>
  13. #include<cstring>
  14. #include<cctype>
  15. #include<cmath>
  16. #include<list>
  17.  #include<iterator>
  18. using namespace std;
  19. typedef  long long ll;
  20. #define FRN(i,a,b) for(ll i=a;i<(ll)b;i++)
  21. #define pb push_back
  22. #define mp make_pair 
  23. #define INF 100000
  24. #define MOD 1000000007
  25. typedef  vector<ll> vi;
  26. typedef  vector<vector<ll> > vvi;
  27. typedef  vector<string> vs;
  28. typedef  vector<double> vd;
  29. typedef  pair<ll,ll> pi;
  30. typedef  map<ll,ll> mii;
  31. typedef  map<string,ll> msi;
  32. typedef  map<ll,string> mis;
  33. typedef  vector<pair<int,int> > vp;
  34. typedef  set<ll> si;
  35. typedef  set<string> ss;
  36. using namespace std;
  37.  
  38. main(){
  39. 	double EPS=.0000000001;
  40. 	int n,m,T,x,y;
  41. 	cin>>T;
  42. 	while(T--){
  43. 	 cin>>n>>m;
  44. 	 double a[n][n];
  45. 	 for(ll j=0;j<m;j++){
  46. 	 cin>>x>>y;
  47. 	  if(x>y){
  48. 	  	double ttt=x*y;
  49. 	  	a[x-1][y-1]=-ttt;
  50. 	  	a[y-1][x-1]=ttt;
  51. 	  }
  52. 	  if(x<y){
  53. 	  	ll ttt=x*y;
  54. 	  	a[x-1][y-1]=ttt;
  55. 	  	a[y-1][x-1]=-ttt;
  56. 	  }
  57. 	}
  58. 	for(int i=0;i<n;i++)a[i][i]=0;
  59. 	double det = 1;
  60. for (int i=0;i<n;++i) {
  61. 	int k = i;
  62. 	for (int j=i+1;j<n;++j)
  63. 		if (abs(a[j][i])>abs(a[k][i]))
  64. 			k=j;
  65. 	if (abs(a[k][i])<EPS) {
  66. 		det = 0;
  67. 		break;
  68. 	}
  69. 	for(int s=i;s<n;s++){
  70. 	double tmp=a[i][s];
  71. 	a[i][s]=a[k][s];
  72. 	a[k][s]=tmp;
  73. 	}
  74. 	if(i!=k)
  75. 		det =-det;
  76. 	det= (det*a[i][i]);
  77. 	for (int j=i+1;j<n;++j)
  78. 		a[i][j]/= a[i][i];
  79. 	for (int j=0;j<n;++j)
  80. 		if (j!=i&&abs(a[j][i])>EPS)
  81. 			for (int k=i+1;k<n;++k)
  82. 				a[j][k]= (a[j][k]-(a[i][k]*a[j][i]));
  83.  
  84. /*for(ll i=0;i<n;i++){
  85. 	for(ll j=0;j<m;j++)cout<<"  "<<a[i][j];
  86.  
  87. cout<<endl;
  88. }*/
  89. }
  90. if(det)cout<<"YES"<<endl;
  91. else cout<<"NO"<<endl; 
  92. }
  93.  
  94. }
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
3
2 2
1 2
1 2
3 2
1 2
2 3
4 6
1 2
1 3
1 4
2 3
2 4
3 4
stdout
copy 
YES
NO
YES
https://ideone.com/zCQTDW
language:
C++ (gcc 8.3)
created:
11 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!