题目

类型：树
image.png

解题思路

待办

代码

  1. class Solution {
  2.     int N = 510;
  3.     int[] cnts = new int[N], fa = new int[N];
  4.     boolean[][] g = new boolean[N][N];
  5.     public int checkWays(int[][] pairs) {
  6.         int m = pairs.length;
  7.         Set<Integer> set = new HashSet<>();
  8.         for (int[] p : pairs) {
  9.             int a = p[0], b = p[1];
  10.             g[a][b] = g[b][a] = true;
  11.             cnts[a]++; cnts[b]++;
  12.             set.add(a); set.add(b);
  13.         }
  14.         List<Integer> list = new ArrayList<>(set);
  15.         Collections.sort(list, (a,b)->cnts[b]-cnts[a]);
  16.         int n = list.size(), root = list.get(0);
  17.         if (m < n - 1) return 0; // 森林
  18.         fa[root] = -1;
  19.         for (int i = 1; i < n; i++) {
  20.             int a = list.get(i);
  21.             boolean ok = false;
  22.             for (int j = i - 1; j >= 0 && !ok; j--) {
  23.                 int b = list.get(j);
  24.                 if (g[a][b]) {
  25.                     fa[a] = b;
  26.                     ok = true;
  27.                 }
  28.             }
  29.             if (!ok) return 0;
  30.         }
  31.         int c = 0, ans = 1;
  32.         for (int i : set) {
  33.             int j = i;
  34.             while (fa[j] != -1) {
  35.                 if (!g[i][fa[j]]) return 0;
  36.                 if (cnts[i] == cnts[fa[j]]) ans = 2;
  37.                 c++;
  38.                 j = fa[j];
  39.             }
  40.         }
  41.         return c < m ? 0 : ans;
  42.     }
  43. }