ulvis.paste.net

Paste Search Dynamic
Recent pastes
dfs
  1. #include <stdio.h>
  2.  
  3. #define MAXN 1024
  4. #define MAXE ((1024*1024)>>5)+1
  5. #define GET(x) (mark[(x)>>5]>>((x)&31)&1)
  6. #define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
  7. int mark[MAXE] = {}, next[MAXN], n, path[MAXN];
  8. int dfs(int u, int dep, int head) {
  9.         if (dep == n)
  10.                 return GET(u<<10);
  11.         for (int pre = -1, cur = head; cur >= 0; pre = cur, cur = next[cur]) {
  12.                 if (!GET(u<<10|cur))
  13.                         continue;
  14.                 if (cur != head) {
  15.                         next[pre] = next[cur];
  16.                         if (dfs(cur, dep+1, head)) {
  17.                                 path[dep] = cur;
  18.                                 return 1;
  19.                         }
  20.                         next[pre] = cur;
  21.                 } else {
  22.                         if (dfs(cur, dep+1, next[cur])) {
  23.                                 path[dep] = cur;
  24.                                 return 1;
  25.                         }
  26.                 }
  27.         }
  28.         return 0;
  29. }
  30. int main() {
  31.         int m, x, y;
  32.         scanf("%d%d", &n, &m);
  33.         for (int i = 0; i < m; i++) {
  34.                 scanf("%d%d", &x, &y);
  35.                 SET(x<<10|y), SET(y<<10|x);
  36.         }
  37.         for (int i = 0; i < n; i++)
  38.                 next[i] = i+1;
  39.         next[n-1] = -1;
  40.         int ret = dfs(0, 1, 1);
  41.         if (ret) {
  42.                 for (int i = 0; i < n; i++)
  43.                         printf("%d ", path[i]);
  44.                 puts("0");
  45.         } else {
  46.                 puts("NO SOLUTION");
  47.         }
  48.         return 0;
  49. }
Parsed in 0.006 seconds