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 ≤ n ≤ 1000 and 0 ≤ m ≤ 10 n. Every given pair of x and y is such that x ≠ 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; } } |
||
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