题解 | #小A最多会新认识的多少人#

#include <iostream>
#include <vector>
#include <set>
using namespace std;

class UnionSet {
private:
    vector<int> parents;
    vector<int> rank;
    
public:
    UnionSet(int n) {
        parents.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
    }
    
    int find(int x) {
        if (parents[x] != x) {
            parents[x] = find(parents[x]);
        }
        return parents[x];
    }
    
    void union_set(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            if (rank[px] > rank[py]) {
                parents[py] = px;
                rank[px] += rank[py];
            } else {
                parents[px] = py;
                rank[py] += rank[px];
            }
        }
    }
    
    int get_rank(int x) {
        return rank[find(x)];
    }
};

int main() {
    int n, A, m;
    cin >> n >> A >> m;
    
    UnionSet us(n);
    set<int> known;
    
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d,%d", &x, &y);
        if (x == A) known.insert(y);
        else if (y == A) known.insert(x);
        us.union_set(x, y);
    }
    
    cout << us.get_rank(A) - 1 - known.size() << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class UnionSet {
        private int[] parents;
        private int[] rank;
        
        public UnionSet(int n) {
            parents = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parents[i] = i;
                rank[i] = 1;
            }
        }
        
        public int find(int x) {
            if (parents[x] != x) {
                parents[x] = find(parents[x]);
            }
            return parents[x];
        }
        
        public void union(int x, int y) {
            int px = find(x), py = find(y);
            if (px != py) {
                if (rank[px] > rank[py]) {
                    parents[py] = px;
                    rank[px] += rank[py];
                } else {
                    parents[px] = py;
                    rank[py] += rank[px];
                }
            }
        }
        
        public int getRank(int x) {
            return rank[find(x)];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int A = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        
        UnionSet us = new UnionSet(n);
        Set<Integer> known = new HashSet<>();
        
        for (int i = 0; i < m; i++) {
            String[] line = sc.nextLine().split(",");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            if (x == A) known.add(y);
            else if (y == A) known.add(x);
            us.union(x, y);
        }
        
        System.out.println(us.getRank(A) - 1 - known.size());
    }
}

class UnionSet:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [1] * n
        
    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            if self.rank[px] > self.rank[py]:
                self.parents[py] = px
                self.rank[px] += self.rank[py]
            else:
                self.parents[px] = py
                self.rank[py] += self.rank[px]

n = int(input())
A = int(input())
m = int(input())

us = UnionSet(n)
known = set()

for _ in range(m):
    x, y = map(int, input().split(','))
    if x == A:
        known.add(y)
    elif y == A:
        known.add(x)
    us.union(x, y)

root = us.find(A)
total = sum(1 for i in range(n) if us.find(i) == root)
print(total - 1 - len(known))