Root = list(map(int, input().split()))
Root_id = Root[1:]

Num = int(input())
Count = 0
Res = []

for i in range(Num):
    Node = list(map(int, input().split()))
    Node_name = Node[0]
    Node_id = Node[2:]

    for j in Node_id:
        if j in Root_id:
            Res.append(Node_name)
            Count += 1
            break

print(Count)
Res.sort()
output = ' '.join(map(str, Res))
print(output)

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <unordered_set>
using namespace std;
typedef long long LL ;
int main()
{
    string s;
    int size1;
    cin>>size1;
    unordered_set<int> set;
    int val;
    for (int i=0; i<size1; i++) {
        cin>>val;
        if (set.find(val)==set.end()) {
            set.insert(val);
        }
    }
    int n;
    cin>>n;
    unordered_set<LL> res;
    for (int i=0; i<n; i++) {
       LL value,t;
       cin>>value;
       cin>> t;
       for (LL j=0; j<t; j++) {
          cin>>val;
          if (set.find(val)!=set.end()) {
            res.insert(value);
          }
       }
    }
    vector<LL> res1=vector<LL>(res.begin(), res.end());
    sort(res1.begin(),res1.end());
    cout<<res1.size()<<endl;
    for (int i=0; i<res1.size(); i++) {
        if (i!=0) {
        cout<<" ";
        }
        cout<<res1[i];
    }

    return 0;
}

#include<iostream>
#include<set>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int main(){
    ll m;  cin >> m;
    set<long long> a_id;
    for(ll i = 0; i < m; i++){
        ll t;      cin >> t;   
        a_id.insert(t);
    }
    int q; cin >> q;
    
    set<ll> vname_set;
    while(q--){
        ll t;
        ll name;    cin >> name; 
        cin >> t;
        bool connected = false;
        for(ll i = 0; i < t; i++){
            ll id;  cin >> id;
            if(a_id.find(id) != a_id.end()){
                connected = true;
            }
        }

        if(connected){
            vname_set.insert(name);
        }
    }
    vector<ll> vname(vname_set.begin(), vname_set.end());
    sort(vname.begin(), vname.end());
    cout << vname.size() << endl;
    for(auto& name : vname){
        cout << name << " ";
    }
    return 0;
}

line1 = list(map(int, input().split()))
m, a_ids = line1[0], line1[1:]
num_nodes = eval(input())
h = dict()
res = []
for item in a_ids:
    h[item] = item 
for i in range(num_nodes):
    line = list(map(int, input().split()))
    name, t, ids = line[0], line[1], line[2:]
    for i in range(t):
        if ids[i] in h:
            res.append(name)
            break

print(len(res))
res.sort()
for i, item in enumerate(res):
    if i == len(res) - 1:
        print(item, end="")
    else:
        print(item, end=" ")

思路：哈希表

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 ) 是其他节点的端口总数量。