#include <stdio.h> #include <vector> using namespace std; int main() { int n; scanf("%d", &n); vector<int> N[n]; for (int i = 0; i < n; i++) { int li; scanf("%d", &li); N[i].resize(li); for (int j = 0; j < li; j++) { scanf("%d", &N[i][j]); N[i][j]--; } } int M[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) M[i][j] = -1; M[i][i] = i; } vector<int> stack; bool is_on_stack[n]; for (int i = 0; i < n; i++) { stack.push_back(i); is_on_stack[i] = true; } while (stack.size() > 0) { int el = stack[stack.size() - 1]; stack.pop_back(); is_on_stack[el] = false; for (int i = 0; i < n; i++) { // check pair i -> el if (M[i][el] == -1) { int maximum = i; for (int v : N[i]) { if (M[v][el] == -1) { maximum = -1; break; } if (M[v][el] > maximum) maximum = M[v][el]; } if (maximum > -1) { M[i][el] = maximum; if (!is_on_stack[i]) { is_on_stack[i] = true; stack.push_back(i); } } } } } int answer[n]; for (int i = 0; i < n; i++) answer[i] = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (M[i][j] != -1) answer[M[i][j]]++; int p = 0; for (int i = 0; i < n; i++) { p += answer[i] - 1; printf("%d ", p); } printf("\n"); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | #include <stdio.h> #include <vector> using namespace std; int main() { int n; scanf("%d", &n); vector<int> N[n]; for (int i = 0; i < n; i++) { int li; scanf("%d", &li); N[i].resize(li); for (int j = 0; j < li; j++) { scanf("%d", &N[i][j]); N[i][j]--; } } int M[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) M[i][j] = -1; M[i][i] = i; } vector<int> stack; bool is_on_stack[n]; for (int i = 0; i < n; i++) { stack.push_back(i); is_on_stack[i] = true; } while (stack.size() > 0) { int el = stack[stack.size() - 1]; stack.pop_back(); is_on_stack[el] = false; for (int i = 0; i < n; i++) { // check pair i -> el if (M[i][el] == -1) { int maximum = i; for (int v : N[i]) { if (M[v][el] == -1) { maximum = -1; break; } if (M[v][el] > maximum) maximum = M[v][el]; } if (maximum > -1) { M[i][el] = maximum; if (!is_on_stack[i]) { is_on_stack[i] = true; stack.push_back(i); } } } } } int answer[n]; for (int i = 0; i < n; i++) answer[i] = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (M[i][j] != -1) answer[M[i][j]]++; int p = 0; for (int i = 0; i < n; i++) { p += answer[i] - 1; printf("%d ", p); } printf("\n"); return 0; } |