2013年8月3日

UVa 10596 - Morning Walk

#include <cstdio>
#include <cstring>

const int MAX = 201;
bool con[MAX][MAX], vis[MAX];

void check(int now) {
  vis[now] = true;
  for (int i = 0; i < MAX; i++) {
    if (!vis[i] && con[now][i]) {
      check(i);
    }
  }
}

int main() {
  int N, R;
  while (scanf("%d%d", &N, &R) == 2) {
    memset(con, 0, sizeof(con));
    memset(vis, 0, sizeof(vis));
    int rec[MAX] = {};
    while (R--) {
      int a, b;
      scanf("%d%d", &a, &b);
      con[a][b] = true;
      rec[a]++;
      rec[b]++;
    }
    int odd = 0;
    for (int i = 0; i < N; i++) {
      if (rec[i] & 1) {
        odd++;
      }
    }
    bool solved = true;
    if (odd) {
      solved = false;
    } else {
      for (int i = 0; i < N; i++) {
        if (rec[i]) {
          check(i);
          break;
        }
      }
      for (int i = 0; i < N; i++) {
        if (!vis[i]) {
          solved = false;
        }
      }
    }
    puts(solved ? "Possible" : "Not Possible");
  }
  return 0;
}

沒有留言:

張貼留言