fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <ctime>
  4. #include <cmath>
  5. #include <cstring>
  6.  
  7. #include <algorithm>
  8. #include <vector>
  9.  
  10. struct mat {
  11.    mat(int dim)
  12.       : n(dim) {
  13.       for (int i = 0; i < n; i++)
  14.          for (int j = 0; j < n; j++)
  15.             d[i][j] = 0.0;
  16.    }
  17.  
  18.    int findMaxInColumn(int c) {
  19.       int max = c;
  20.       for (int i = c + 1; i < n; i++)
  21.          if (fabs(d[i][c]) > fabs(d[max][c]))
  22.             max = i;
  23.       return max;
  24.    }
  25.  
  26.    void swapRow(int r1, int r2) {
  27.       for (int j = 0; j < n; j++)
  28.          std::swap(d[r1][j], d[r2][j]);
  29.    }
  30.  
  31.    bool gaussian() {
  32.       for (int i = 0; i < n; i++) {
  33.          int m = findMaxInColumn(i);
  34.  
  35.          if (m != i)
  36.             swapRow(i, m);
  37.  
  38.          if (fabs(d[i][i]) < 1e-9)
  39.             return false;
  40.  
  41.          for (int j = i + 1; j < n; j++) {
  42.             double q = d[j][i] / d[i][i];
  43.             for (int k = i; k < n; k++)
  44.                d[j][k] -= q * d[i][k];
  45.             d[j][i] = 0;
  46.          }
  47.       }
  48.  
  49.       return true;
  50.    }
  51.  
  52.    double determinant() {
  53.       double det = 1;
  54.       for (int i = 0; i < n; i++)
  55.          det *= d[i][i];
  56.       return det;
  57.    }
  58.  
  59.    void dump() {
  60.       for (int i = 0; i < n; i++) {
  61.          for (int j = 0; j < n; j++)
  62.             printf("%lf ", d[i][j]);
  63.          printf("\n");
  64.       }
  65.    }
  66.  
  67.    int     n;
  68.    double  d[100][100];
  69. };
  70.  
  71. struct edge {
  72.    int a, b;
  73. };
  74.  
  75. int main(int argc, char* argv[]) {
  76.    srand(time(NULL));
  77.  
  78.    int t;
  79.    scanf("%d", &t);
  80.    while (t--) {
  81.       int n, m;
  82.       scanf("%d %d", &n, &m);
  83.  
  84.       std::vector<edge> edges;
  85.       for (int i = 0; i < m; i++) {
  86.          edge e;
  87.          scanf("%d %d", &e.a, &e.b);
  88.          e.a--; e.b--;
  89.          edges.push_back(e);
  90.       }
  91.  
  92.       bool pm = false;
  93.       if ((n % 2) == 0) {
  94.          // || (m < (n / 2))
  95.          // || (n > 50)) {
  96.          for (int k = 0; k < 10; k++) {
  97.             mat mtx(n);
  98.             for (unsigned int i = 0; i < edges.size(); i++) {
  99.                const edge& e = edges[i];
  100.                int v = rand() % 1000000007;
  101.                mtx.d[e.a][e.b] = v; mtx.d[e.b][e.a] = -v;
  102.             }
  103.  
  104.             if (mtx.gaussian()) {
  105.             // && (fabs(mtx.determinant()) > 1e-9)) {
  106.                pm = true;
  107.                break;
  108.             }
  109.  
  110.             mtx = mat(n);
  111.          }
  112.       }
  113.  
  114.       printf(pm ? "YES\n" : "NO\n");
  115.    }
  116.  
  117.    return 0;
  118. }
  119.  
Success #stdin #stdout 0s 3476KB
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/xOI0j5
language:
C++ (gcc 8.3)
created:
10 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!