思路：哈希表

1. 输入解析：

   • 读取节点 ( A ) 的端口数量及其每个端口的连通块 ID。用一个集合 a_blocks 来存储这些 ID，以便后续快速查询。
   • 读取其他节点的数量和其详细信息，逐个处理。

2. 连通性判断：

   • 对于每个节点，遍历其端口的连通块 ID，判断这些 ID 是否与 a_blocks 有交集（即是否存在至少一个 ID 属于 a_blocks）。
   • 如果找到连通块 ID 与 a_blocks 中的任一 ID 相同，则说明该节点与节点 ( A ) 连通。
   • 将连通的节点记录下来。

3. 输出：

   • 输出连通节点的数量。
   • 将所有连通的节点名称排序后输出。

实现细节

1. 使用集合（Set）来存储节点 ( A ) 的端口 ID，因为集合可以加快查找的速度。
2. 对每个其他节点的端口 ID 使用集合的交集运算，判断是否与 a_blocks 有交集。
3. 使用列表存储所有连通的节点名称，最终排序输出。

代码

C++

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 读取节点A的端口数量及其端口ID集合
    int m;
    cin >> m;
    set<int> aBlocks;
    for (int i = 0; i < m; i++) {
        int portId;
        cin >> portId;
        aBlocks.insert(portId);
    }

    // 读取其他节点数量
    int n;
    cin >> n;
    vector<unsigned long long> connectedNodes;

    // 处理每个节点的信息
    for (int i = 0; i < n; i++) {
        unsigned long long name;
        int t;
        cin >> name >> t;
        bool isConnected = false;

        // 检查节点的每个端口ID是否与节点A连通
        for (int j = 0; j < t; j++) {
            int portId;
            cin >> portId;
            if (aBlocks.count(portId)) {
                isConnected = true;
            }
        }

        // 如果连通，将节点名称加入连通节点列表
        if (isConnected) {
            connectedNodes.push_back(name);
        }
    }

    // 对连通节点名称进行排序并输出
    sort(connectedNodes.begin(), connectedNodes.end());
    cout << connectedNodes.size() << endl;
    for (unsigned long long node : connectedNodes) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

python代码

# 读取节点A的信息
m, *a_ports = map(int, input().split())
a_blocks = set(a_ports)  # 使用集合存储节点A的端口ID

# 读取其他节点的数量
n = int(input())
connected_nodes = []

# 遍历每个节点
for _ in range(n):
    data = list(map(int, input().split()))
    name, t, ports = data[0], data[1], data[2:]
    
    # 检查当前节点是否与节点A连通
    if a_blocks.intersection(ports):
        connected_nodes.append(name)

# 输出结果
connected_nodes.sort()
print(len(connected_nodes))
print(" ".join(map(str, connected_nodes)))

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取节点A的端口数量
        int m = scanner.nextInt();
        
        // 使用Set存储节点A的端口ID，以便快速查找
        Set<Long> set = new HashSet<>();
        for (int i = 0; i < m; i++) {
            set.add(scanner.nextLong());
        }
        
        // 读取其他节点的数量
        int n = scanner.nextInt();
        
        // 使用 TreeSet 存储结果节点名称，自动排序
        TreeSet<Long> res = new TreeSet<>();
        
        // 处理输入的其他节点
        scanner.nextLine(); // 清空当前行
        for (int i = 0; i < n; i++) {
            String[] str = scanner.nextLine().split(" ");
            
            // 读取节点的名称
            Long node = Long.parseLong(str[0]);
            boolean flag = false; // 用于标识是否连通

            // 从端口ID开始遍历，检查是否有与节点A连通的端口
            for (int j = 2; j < str.length; j++) {
                if (set.contains(Long.parseLong(str[j]))) {
                    // 如果有连通的端口，记录该节点名称，并设置连通标志
                    flag = true;
                    break;
                }
            }

            // 如果节点与A连通，将其名称加入结果集合
            if (flag) {
                res.add(node);
            }
        }

        // 输出连通节点的数量
        System.out.println(res.size());
        
        // 输出连通节点的名称
        int sum = 1;
        for (long node : res) {
            if (sum == res.size()) {
                System.out.print(node);
            } else {
                System.out.print(node + " ");
            }
            sum++;
        }
    }
}

复杂度分析

• 时间复杂度：由于我们遍历每个节点并检查其端口的连通块 ID，整体时间复杂度为 ( O(n \cdot t) )，其中 ( n ) 是节点数，( t ) 是每个节点的端口数量。这在给定的范围内是可行的。
• 空间复杂度：主要使用集合和列表来存储端口 ID 和连通节点名称，因此空间复杂度为 ( O(m + t) )，其中 ( m ) 是节点 ( A ) 的端口数量，( t ) 是其他节点的端口总数量。

题目内容

塔子哥搭建了一个网络，网络中存在有$N$个网络节点，并且每个节点被塔子哥赋予了一个唯一的标识Name。每个节点有$t$个端口，节点间通过端口进行报文通讯。同时，塔子哥为了满足服务需求，将节点的每个端口进行了连通块的划分(所处连通块用id标识)：

1. 如果两个端口的id相同，说明这两个端口处于同一个连通块中，处于连通状态
2. 否则，彼此不连通

塔子哥想知道，有哪些节点和节点$A$是连通的？(有一个端口和$A$在同一个连通块中就能与A连通)

输入描述

第一行一个整数$m$及$m$个整数，代表节点$A$的端口数量以及每个端口的id。

第二行一个整数$n$，代表网络中除节点$A$外，还有其他$n$个节点。

接下来$n$行，每行形式为$Name\space t\space id_1\space id_2...id_t$

$0\le n\le4000$

$1\le Name\le4294967294$

输出描述

第一行一个整数$N$，代表与$A$连通的节点一共有多少个。

第二行$N$个整数，代表每个节点的$Name$，从小到大输出。

样例

输入

2 1 2
4
1000 3 4 3 5
1001 2 1 2
114514 3 1 2 3
1919810 1 1

输出

3
1001 114514 1919810