Much more efficiently, please! P21551

Statement

Write a program to computes the same as the program below, but much more efficiently, both in space and in time. The read variables n and m are such that $1 \le \texttt{n} \le 1000$ and $0 \le \texttt{m} \le 10 \texttt{n}$ . Every given pair of x and y is such that $\texttt{x} \ne \texttt{y}$ .


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


const int INF = 1000000000;
typedef vector<int> VI;
typedef vector<VI> VVI;


int n, m;
VVI G;
int C[1000];


bool OK1(VVI A) {
  for (int x = 0; x < n; ++x) A[x][x] = 0;

  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        A[i][j] = min(A[i][j],
                      A[i][k] + A[k][j]);

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (A[i][j] == INF) return false;
  return true;
}


bool OK2(int i) {
  if (i == n) return true;

  vector<bool> U(2, false);
  for (int j = 0; j < i; ++j)
    if (G[i][j] == 1) U[C[j]] = true;

  for (int k = 0; k < 2; ++k)
    if (not U[k]) {
      C[i] = k;
      if (OK2(i + 1)) return true;
    }
  return false;
}


int main() {
  while (cin >> n >> m) {
    G = VVI(n, VI(n, INF));
    while (m--) {
      int x, y;
      cin >> x >> y;
      G[x][y] = G[y][x] = 1;
    }

    if (not OK1(G)) cout << "NC" << endl;
    else if (OK2(0)) cout << "yes" << endl;
    else cout << "no" << endl;
  }
}

Public test cases

Input

5 4    0 1  1 3  2 4  3 0
6 7    0 1  1 2  2 3  3 4  4 5  5 0  0 3
5 5    2 1  0 1  3 4  4 0  2 3

Output

NC
yes
no

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++