树每个节点的孩子数量

解题思路

每个节点的孩子数量都等于与它关联的节点数量 - 1 (根节点除外)

时间复杂度

$O(n^2)$

#include<iostream>
using namespace std;
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int cnt = 0;   // 与节点i关联的节点数量
    for (int j = 1; j <= n; j++) {
      char x;
      cin >> x;
      if (x == '1') cnt++;   // 如果x为1, 说明i和j有边, cnt + 1
    }
    if (i == 1) cout << cnt << ' ';  // 如果i为1, 说明i是根节点, 直接输出cnt
    else cout << cnt - 1 << ' ';    // 否则输出 cnt - 1
  }
  return 0;
}