小A最多会新认识的多少人

# 方法和之前用Python的那位是一模一样的，只不过写了个并查集的类来实现，我自己是AC了的
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]
import sys
lines = sys.stdin.readlines()
n = int(lines[0].strip())
A = int(lines[1].strip())
us = UnionSet(n)
seen = set()
for line in lines[3:]:
    i, j = list(map(int, line.split(',')))
    if i == A:
        seen.add(j)
    elif j == A:
        seen.add(i)
    us.union(i, j)
ans = 0
root = us.find(A)
for i in range(n):
    if us.find(i) == root:
        ans += 1
print(ans - 1 - len(seen))

//顺便复习下并查集，很重要的东东
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()) {
			
			int n = sc.nextInt();
			
			int bianhao = sc.nextInt();
			
			int renshi = sc.nextInt();
		 
			ArrayList<Integer> arrList = new ArrayList<Integer>();
			for(int i=0;i<n;i++) {
				arrList.add(i);
			}
			UnionFindSet ufs = new UnionFindSet(arrList);
			
			int hasRenshi = 0;
			for(int i=0;i<renshi;i++) {
				String s = sc.next();
				
				String[] sarr = s.split(",");
				
				String s1 = sarr[0];
				String s2 = sarr[1];
				Integer i1 = Integer.valueOf(s1);
				Integer i2 = Integer.valueOf(s2);
				
				if(i1.equals(bianhao) || i2.equals(bianhao)) {
					hasRenshi ++;
				}
				
				ufs.union(i1, i2);
				 
			}
			int size = ufs.sizeMap.get(ufs.findHead(ufs.getElementMap().get(bianhao)));
			 
			System.out.println(size - 1 - hasRenshi);
	 
			 
  
		}
	}
	
	
	public static class Element {
		public int value;

		public Element(int value) {
			this.value = value;
		} 
	}
	
	public static class UnionFindSet{
		public HashMap<Integer,Element> elementMap;
		// key  某个元素  value 该元素的父
		public HashMap<Element, Element> fatherMap;
		// key 某个集合的代表元素   value 该集合的大小
		public HashMap<Element, Integer> sizeMap;
		
		public UnionFindSet(ArrayList<Integer> arrList) {
			elementMap = new HashMap<>();
			fatherMap = new HashMap<>();
			sizeMap = new HashMap<>();
			
			for(Integer item:arrList) {
				Element ele = new Element(item);
				elementMap.put(item, ele);
				fatherMap.put(ele, ele);
				sizeMap.put(ele, 1);
			}
		}
		public HashMap<Integer,Element> getElementMap(){
			return elementMap;
		}
		public Element findHead(Element ele) {
			Stack<Element> stack = new Stack();
			
			while(ele != fatherMap.get(ele)) {
				stack.add(ele);
				ele = fatherMap.get(ele);
			}
			
			while(!stack.isEmpty()) {
				fatherMap.put(stack.pop(), ele);
			}
			
			return ele;
		}
		
		public boolean isSameSet(Integer a, Integer b) {
			if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
				return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
			}
			return false;
		}
		public void union(Integer a, Integer b) {
			if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
				Element aF = findHead(elementMap.get(a));
				Element bF = findHead(elementMap.get(b));
				if (aF != bF) {
					Element big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
					Element small = big == aF ? bF : aF;
					fatherMap.put(small, big);
					sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF));
					sizeMap.remove(small);
				}
			}
		}
		
		
	}

}

people = int(input())
target = int(input())
t = int(input())
parent = [i for i in range(people)]
rank = [1] * people
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    px, py = find(x), find(y)
    if px != py:
        if rank[px] >= rank[py]:
            rank[px] += rank[py]
            parent[py] = px
        else:
            parent[px] = py
            rank[py] += rank[px]
seen = set()
for _ in range(t):
    p1, p2 = list(map(int, input().split(',')))
    union(p1, p2)
    if p1 == target:
        seen.add(p2)
    elif p2 == target:
        seen.add(p1)
if len(seen) == 0:
    print(0)
count = 0
root= find(target)
for i in range(people):
    if find(i) == root:
        count += 1
print(count - 1 - len(seen))

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 8;
vector<int> G[maxn];
int res = 0;

//深度遍历 找到一个集合的人
void dfs(int ai, vector<bool> &v) {
	for (int i = 0; i < G[ai].size(); ++i) {
		if (!v[G[ai][i]]) {
			v[G[ai][i]] = true;
			res++;
			dfs(G[ai][i], v);
		}	

	}
	return;
}


int main() {
	int n, ai, m;
	cin >> n >> ai >> m;
    //构建邻接表
	while (m--) {
		int p1, p2;
		char chs;
		cin >> p1 >> chs >> p2;
		G[p1].push_back(p2);
		G[p2].push_back(p1);
		
	}
	vector<bool> visited(n, false);
    
    //除去本来就认识的人和自己
	int already = G[ai].size() + 1;
	dfs(ai,visited);

	cout << res - already << endl;

	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int p[10001];
int findParent(int x){
    return (p[x]==x)?x:p[x]=findParent(p[x]);
}

int main(){
    int n,m,t,cnt=0;
    cin>>n>>t>>m;
    for(int i=0;i<n;i++)
        p[i] = i;

    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d,%d", &a, &b);
        int pa = findParent(a);
        int pb = findParent(b);
        if(a==t || b==t)
            cnt--;
        if(pa != pb)
            p[pa] = pb;
    }
    for(int i=0;i<n;i++)
        if(findParent(i) == findParent(t))
            cnt++;
    cout<<cnt-1<<endl;
    return 0;
}

//并查集基本应用，最后别忘了减掉本身
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,ix,m;
vector<int>f;
int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}
int main(void){
    cin>>n>>ix>>m;
    f=vector<int>(n);
    for(int i=0;i<n;i++)f[i]=i;
    int ans=0,b=0;
    while(m--){
        int one,two;
        scanf("%d,%d",&one,&two);
        if(one==ix||two==ix)b++;
        int fx=find(one),fy=find(two);
        if(fx!=fy)f[fx]=fy;
    }
    for(int i=0;i<n;i++){
        if(find(ix)==find(i))ans++;
    }
    cout<<ans-b-1<<endl;
    return 0;

}

//广度优先搜索，最后一个列子没通过，时间不够了
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    int n;
    cin >> n;
    int numiofA;
    cin >> numiofA;
    int m;
    cin >> m;
    vector<pair<int, int>> friends;
    int no1, no2;
    char ch;
    while (cin >> no1 >> ch >> no2) {
        friends.emplace_back(no1, no2);
    }
    int ans=0;
    queue<int>q;
    vector<int>arr(n);
    for (int i = 0; i < m; i++) {
        if (friends[i].first == numiofA) {
            q.push(friends[i].second);
            arr[friends[i].second] = 2;//本来就认识，ans不++
        }
        if (friends[i].second == numiofA) {
            q.push(friends[i].first);
            arr[friends[i].first] = 2;
        }
    }
    arr[numiofA] = 2;
    while (!q.empty()) {
        auto x = q.front();
        q.pop();
        int nn=friends.size();
        for (int i = 0; i < nn; i++) {
            if (friends[i].first == x && arr[friends[i].second] == 0) {
                q.push(friends[i].second);
                arr[friends[i].second] = 1;
                ans++;
            }
            if (friends[i].second == x && arr[friends[i].first] == 0) {
                q.push(friends[i].first);
                arr[friends[i].first] = 1;
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

class DSU:
    def __init__(self,n: int):
        self.p = [i for i in range(n)]
        self.cnt = [1] * n
    
    def find(self,x: int) -> int:
        if x != self.p[x]: self.p[x] = self.find(self.p[x])
        return self.p[x]
    
    def merge(self,x: int,y: int):
        rx , ry = self.find(x) , self.find(y)
        if rx == ry: return 
        self.p[rx] = ry
        self.cnt[ry] += self.cnt[rx]
        return 
def main():
    n = int(input())
    dsu = DSU(n)
    p = int(input())
    m = int(input())
    res = 0
    for _ in range(m):
        a ,b = map(int,input().split(','))
        if a == p:
            res -= 1
        if b == p:
            res -= 1
        dsu.merge(a,b)
    fa = dsu.find(p)
    print(dsu.cnt[fa] + res - 1)

if __name__ == '__main__':
    main()

图的数据结构必须邻接矩阵，简直裂开！

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine());
        int ai = Integer.parseInt(reader.readLine());
        int m = Integer.parseInt(reader.readLine());

        int[][] pairs = new int[m][2];
        for (int i = 0; i < m; i++) {
            String[] D = reader.readLine().split(",");
            pairs[i][0] = Integer.parseInt(D[0]);
            pairs[i][1] = Integer.parseInt(D[1]);

        }
        Map<Integer, ArrayList<Integer>> A = new HashMap<>();
        for (int[] pair : pairs) {
            if (!A.containsKey(pair[0])) {
                A.put(pair[0], new ArrayList<>());
            }
            if (!A.containsKey(pair[1])) {
                A.put(pair[1], new ArrayList<>());
            }
            A.get(pair[0]).add(pair[1]);
            A.get(pair[1]).add(pair[0]);
        }

        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> hasVisited = new HashSet<>();
        queue.add(ai);
        int res = 0;
        while (!queue.isEmpty()) {
            int idx = queue.poll();
            if (hasVisited.contains(idx)) {
                continue;
            }
            if (A.get(idx) != null) {
                for (int num : A.get(idx)) {
                    queue.add(num);
                }
            }
            hasVisited.add(idx);
            res++;
        }
        if (A.get(ai) != null) {
            res -= A.get(ai).size();
        }
        res-=1;
        writer.write(String.valueOf(res));

        reader.close();
        writer.close();
    }
}

//并查集求联通块内的点数量，但是要减去时间相连的，用hashset存一下就好了
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    static int N = 10010, n, start, m;
    static int[] p = new int[N], cnt = new int[N];

    static int find(int x){
        if(p[x] != x)
            p[x] = find(p[x]);
        return p[x];
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); start = in.nextInt(); m = in.nextInt();

        for(int i = 0; i < n; i ++) p[i] = i;
        HashSet<Integer> set = new HashSet<>();
        Arrays.fill(cnt, 1);
        for(int i = 1; i <= m; i ++){
            String[] arr = in.next().split(",");
            int a = Integer.parseInt(arr[0]), b = Integer.parseInt(arr[1]);
            if(a == start || b == start){
                set.add(a); set.add(b);
            }
            int pa = find(a),  pb = find(b);
            if(pa != pb){
                p[pa] = pb;
                cnt[pb] += cnt[pa];
            }
        }
        System.out.println( cnt[find(start)] - set.size());
    }

}

// Union_Find_Algorithm

#include <stdio.h>
#include <stdlib.h>

// Path Compression （路径压缩）
int Find(int* p, const int x) {
  return *(p + x) = *(p + x) ^ x ? Find(p, *(p + x)) : x;
}

// Union By Rank (暂不考虑按秩合并)
void Union(int* p, const int u, const int v) {
  *(p + Find(p, u)) = *(p + Find(p, v));
}

int main(const int argc, const char* argv[]) {
  int n, ai, m, i;
  fscanf(stdin, "%d %d %d", &n, &ai, &m);
  
  int p[n];
  for (i = 0; i < n; ++i) *(p + i) = i;
  
  int u, v, count = 1;
  while (m--) {
    fscanf(stdin, "%d,%d", &u, &v);
    if (u == ai || v == ai) ++count;
    Union(p, u, v);  
  }
  
  int cnt = 0, pid = Find(p, ai);
  for (i = 0; i < n; ++i)
    cnt += Find(p, i) == pid;
  
  return printf("%d", cnt - count), 0;
}

#include <vector>

using namespace std;

void depth_first_search_algorithm(vector<vector<int>>& g,
                                  vector<int>& seen,
                                  int cur,
                                  int& ccs) {
  if (seen[cur]++) return;
  
  ++ccs;
  for (int nxt : g[cur])
    depth_first_search_algorithm(g, seen, nxt, ccs);
}

int main(const int argc, const char** argv) {
  int n, ai, m, count = 1;
  cin >> n >> ai >> m;
  
  vector<vector<int>> g(n);
  vector<int> seen(n, 0);
  
  int a, b;
  while (m--) {
    fscanf(stdin, "%d, %d", &a, &b);
    if (a == ai || b == ai) ++count;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  
  int ccs = 0; // connected component size ; // 连通分量的大小
  depth_first_search_algorithm(g, seen, ai, ccs);
  cout << ccs - count;
  return 0;
}

import java.util.HashSet;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        UF uf = new UF(Integer.parseInt(scanner.nextLine()));
        int a = Integer.parseInt(scanner.nextLine());
        int m = Integer.parseInt(scanner.nextLine());
        int b = 0;
        int ans = 0;
        HashSet<Integer> set = new HashSet<>();
        while (m > 0){
            String[] str = scanner.nextLine().split(",");
            int i = Integer.parseInt(str[0]);
            int j = Integer.parseInt(str[1]);
            if(i == a || j == a) b++;
            set.add(i);
            set.add(j);
            uf.union(i,j);
            m--;
        }
        for (Integer integer : set) {
            if(uf.connected(a,integer)) ans++;
        }
        System.out.println(ans - b - 1);
    }
}

class UF {
    private int[] parent;
    private int[] size;

    public UF(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;

        // 小树接到大树下面，较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
    }

    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    private int find(int x) {
        while (parent[x] != x) {
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

}