语言月赛 202407【significance】题解（AC）

》》》点我查看「视频」详解》》》

[语言月赛 202407] significance

题目背景

从前有个荣光的王国，小 A 是里面的国王，他认为人活着需要有意义，所以今天他要赐予他的子民以意义。

题目描述

细心的小 A 发现，每个人的存在对于其他人来说都有着不可取代的意义。一个人的意义值定义为他的朋友和朋友的朋友的个数。

小 A 的王国共有 $n$ 位居民，以 $1,2,\cdots ,n$ 编号。每位居民分别有 $x_i$ 个朋友，现在小 A 想知道每位居民的意义值。

注意，朋友关系可能是单向的。即：有可能 $a$ 把 $b$ 当朋友，但 $b$ 不一定把 $a$ 当作朋友。同时，如果一个人的朋友的朋友中有自己，则这一部分的个数不统计。

时光荏苒，朋友的联系也会散去。而我们和一个人保持连接的方式就是记住，仅此而已。

输入格式

第一行一个整数 $n$ 表示小 A 王国的居民数。

接下来 $n$ 行每行 $x_i+1$ 个整数。第一个整数 $x_i$ 表示 $i$ 号居民有几个朋友，接下来 $x_i$ 个整数分别表示他的朋友的编号。

输出格式

一行 $n$ 个整数分别表示每位居民的意义值。

样例 #1

样例输入 #1

4
2 2 3
1 4
0
0

样例输出 #1

3 1 0 0

样例 #2

样例输入 #2

3
0
2 1 3
0

样例输出 #2

0 2 0

样例 #3

样例输入 #3

3
1 2
1 3
1 1

样例输出 #3

2 2 2

提示

样例 1 解释

• $1$ 号居民认为他的朋友是 $2$ 和 $3$，$3$ 认为自己没有朋友，但 $2$ 认为自己有一个朋友 $4$, 所以 $1$ 号居民的意义值是 $3$。
• $2$ 号居民认为他的朋友是 $4$，$4$ 没有朋友，所以 $2$ 号居民的意义值是 $1$。
• $3$ 号和 $4$ 号居民都认为自己没有朋友，所以他们的意义值是 $0$。

样例 2 解释

• $1$ 号和 $3$ 号居民认为他们没有朋友，所以他们的意义值是 $0$。
• $2$ 号居民的朋友是 $1$ 和 $3$，$1,3$ 都认为自己没有朋友，所以 $2$ 号居民的意义值是 $2$。

样例 3 解释

• $1$ 号居民认为他的朋友是 $2$, $2$ 认为他的朋友是 $3$，所以 $1$ 号居民的意义值是 $2$。
• $2$ 号居民的朋友是 $3$，$3$ 认为自己的朋友是 $1$，所以 $2$ 号居民的意义值是 $2$。
• $3$ 号居民的朋友是 $1$，$1$ 认为自己的朋友是 $2$，所以 $3$ 号居民的意义值是 $2$。

数据范围

• 对于 $20\%$ 的数据，$x_i\le 1$ 。
• 对于另外 $20\%$ 的数据，除 $x_1=n-1$ 外， $x_i=0$ 。
• 对于 $100\%$ 的数据，$1\le n\le 100$，$0\le x_i\le n$。保证每一行除第一个数外的其他整数 $c$ 均有 $1\le c\le n$ 且两两不同。
• 数据保证不会出现「一个人是自己的朋友」，或者「一个人既是另一个人的朋友，又是他朋友的朋友」的情况。

AC_Code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int t[N]; // t[i] 表示i有多少个朋友
int g[N][N]; // g[i][j] 表示第i个居民的第j个朋友是谁
bool st[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> t[i];
        for(int j = 0; j < t[i]; j ++)
        {
            cin >> g[i][j];
        }
    }


    for(int i = 1; i <= n; i ++)
    {
        memset(st, 0, sizeof st);
        int ans = 0;
        for(int j = 0; j < t[i]; j ++)
        {
            int x = g[i][j];
            st[x] = true;
            for(int k = 0; k < t[x]; k ++)
            {
                int y = g[x][k];
                st[y] = true;
            }
        }

        for(int j = 1; j <= n; j ++)
            if(i != j && st[j])
                ans ++;
        cout << ans << " ";
    }

    return 0;
}

》》》点我查看「视频」详解》》》