朋友圈(后端开发卷)

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<int, int> fa;  //用fa来存储父节点
unordered_map<int, int> cnt;  //用cnt来存储节点的子节点数量

int find(int x)  //寻找父节点
{
    if (fa.find(x) == fa.end()) {  //fa[x]尚未存在表中时
        fa[x] = x;  //将fa[x]的父节点设置为自己
        cnt[x] = 0;
    }
    if (x == fa[x]) {
        return x;
    }
    return fa[x] = find(fa[x]);  //将x的根节点设置为父节点(路径压缩),并返回根节点
}

void Union(int x, int y)  //合并
{
    int fx = find(x);  //fx为x的父节点
    int fy = find(y);  //fy为y的父节点
    fa[fx] = fy;  //将fx的父节点设为fy
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        while (n--)
        {
            int x, y;
            cin >> x >> y;
            Union(x, y);
        }
        int ans = 0;  //每个节点子节点数至少为1（其自身），故将初始ans设置为0用于后续比较
        for (unordered_map<int,int>::iterator it=fa.begin();it!=fa.end(); it++)
        {
            int fi = find(it->second);
            cnt[fi]++;  //每到节点i就往其根节点cnt[]+1
            if (cnt[fi] > ans)
                ans = cnt[fi];
        }
        cout << ans << endl;
        fa.clear();
        cnt.clear();
    }
    return 0;
}

//  邻接表 + dfs
#include<iostream>
#include<vector>
using namespace std;
int cnt,ans;
int v[100001];
vector<int>a[100001];
void dfs(int x)
{
    int i,num;
    v[x]=1; cnt++;
    for(i=0;i<a[x].size();i++)
    {
        num=a[x][i];
        if(v[num]==0)dfs(num);
    }
}
int main()
{
    int i,k,n,x,y,T;
    scanf("%d",&T);
    for(i=0;i<T;i++)
    {
        scanf("%d",&n);
        for(k=1;k<=1e5;k++)
        {
            v[k]=0;
            a[k].clear();
        }
        for(k=1;k<=n;k++)
        {
            scanf("%d %d",&x,&y);
            a[x].push_back(y);
            a[y].push_back(x);
        }
        ans=0;
        for(k=1;k<=1e5;k++)
        {
            cnt=0;
            dfs(k);
            ans=max(ans,cnt);
        }
        printf("%d\n",ans);
    }
    return 0;
}

使用并查集，并添加路径压缩。关于并查集和路径压缩的讲解见并查集

详细注释代码如下：

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(); // t组数据
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt(); // n对关系
            HashMap<Integer,Integer> map = new HashMap<>(); // 用户数字 到 数组位置 的映射
            int[] check = new int[n * 2]; // 并查集数组（n对，最多 n * 2 个用户）

            for (int j = 0; j < n * 2; j++) { // 初始化并查集，指向自己
                check[j] = j;
            }

            for (int j = 0; j < n; j++) { // 建立并查集
                int a = sc.nextInt(); // 读入用户对
                int b = sc.nextInt();
                int x = map.getOrDefault(a, map.size()); // 找到映射
                map.put(a, x);
                int y = map.getOrDefault(b, map.size());
                map.put(b, y);

                if (find(check, x) != x && find(check, y) != y) { // 当都有根，从根部联通两并查集，能减少find的次数
                    check[find(check, x)] = find(check, y); // (连接方式未优化）
                } else if (find(check, x) != x) { // 只有一方有根，另一方直接连到根；都没根时一样
                    check[y] = find(check, x);
                } else {
                    check[x] = find(check, y);
                }
            }

            HashMap<Integer,Integer> res = new HashMap<>(); // 并查集根 和 并查集节点个数 的映射
            for (int j = 0; j < n * 2; j++) { // 遍历并查集
                int k = find(check, j); // 找到当前节点的根
                res.put(k, res.getOrDefault(k, 0) + 1); // 节点个数加一
            }

            int max = 0;
            for (Integer value : res.values()) { // 遍历各个并查集的节点个数，找出最大者
                max = Math.max(max, value);
            }

            System.out.println(max); // 打印
        }
    }

    // 查找并查集的根
    private static int find(int[] check, Integer i) {
        if (check[i] != i) { // 当前节点非根
            check[i] = find(check, check[i]); // 当前节点指向根（路径压缩）
        }
        return check[i]; // 返回根
    }
}

#include <bits/stdc++.h>

using namespace std;

int total_t, n;


int NumofLargestGroup(vector<int>* mat, int n)
{
    if(!n)
        return n;
    vector<bool> visited(10000005, false);
    int ans = 0;
    
    stack<int> s;
    
    for(int i = 1; i <= 10000000; ++i)
    {
        if(visited[i] || mat[i].empty())
            continue;
        s.push(i);
        
        int cur_ans = 0;
        while(!s.empty())
        {
            int cur = s.top();
            s.pop();
            
            if(visited[cur])
                continue;
            visited[cur] = true;
            ++cur_ans;
            for(const auto& fr : mat[cur])
            {
                
                //cout << "cur " << cur <<" fr " << fr << endl;
                if(visited[fr])
                    continue;
                s.push(fr);
            }
        }
        ans = max(ans, cur_ans);
            
    }
    return ans;
}


int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> total_t;
    
    while(total_t--)
    {
        vector<int> mat[10000005];
        
        
        cin >> n;
        int a, b;
        for(int i = 1; i <= n; ++i)
        {
            cin >> a >> b;
            
            mat[a].push_back(b);
            mat[b].push_back(a);
        }
        
        cout << NumofLargestGroup(mat, n) << endl;
    }
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 1e5 + 5;
int parent[MAX_N];
int sz[MAX_N];

int find(int x) {
    if (x == parent[x]) {
        return x;
    }
    parent[x] = find(parent[x]);
    return parent[x];
}

void merge(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px == py) {
        return;
    }
    parent[py] = px;
    sz[px] += sz[py];
}


int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int m;
        cin >> m;
        unordered_set<int> set;
        for (int i = 0; i < MAX_N; i++) {
            sz[i] = 1;
            parent[i] = i;
        }
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            set.insert(x);
            set.insert(y);
            merge(x, y);
        }
        int ans = 0;
        for (auto x : set) {
            ans = max(ans, sz[find(x)]);
        }
        cout << ans << endl;
    }

    return 0;
}

#参考https://oi-wiki.org/ds/dsu/
class Dsu:
    def __init__(self,size):
        self.pa = list(range(size))
        self.size = [1]*size
        self.max_size=1
    def find(self,x): #沿着树向上找到x的根节点，并将查询过程中经过的每个元素都归到根节点（路径压缩）
        if self.pa[x]!=x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]
    def union(self,x,y):# 将x的根节点接到y,
        #启发式合并，将小的树合并到大的树
        x,y = self.find(x),self.find(y)
        if x==y: return
        if self.size[x]<self.size[y]:
            x,y=y,x
        self.pa[y]=x
        self.size[x]+=self.size[y]
        if self.size[x]>self.max_size:
            self.max_size=self.size[x]
            
        
while True:
    try:
        T=int(input())
        for _ in range(T):
            n = int(input())
            dsu = Dsu(100000+1)
            
            for _ in range(n):
                x,y=list(map(int,input().split()))
                dsu.union(x,y)
                
            print(dsu.max_size)
            del dsu
        
    except: break

import java.util.*;

public class Main {
    /*
        整体背景就是一堆孩子 认爹 
        然后看哪个爹孩子最多（还要加上老爹）
      */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //一共几组数据
        for (int i = 0; i < n; i++) {
            //找自己的爹节点 如果parent中不存在自己 那么说明自己没有爹节点
            //自己就是自己的爹
    
            Map<Integer, Integer> parent = new HashMap<Integer, Integer>();
            
            //哪个爹有多少个孩子  key是爹  value是孩子的数量
            Map<Integer, Integer> sizeMap = new HashMap<Integer, Integer>();
            int m = sc.nextInt();
            for (int j = 0; j < m; j++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                //分别找爹 看看谁的爹大
                int pa= find(parent,a);
                int pb= find(parent,b);
                //如果你爹不等于我爹
                if (pa!=pb){
                    //那么你pb要认我为爹
                    parent.put(pb, pa);
                    //你pb家族的孩子都归我们家族了
                    int pbSize = sizeMap.getOrDefault(pb, 1);
                    int paSize = sizeMap.getOrDefault(pa, 1);
                    sizeMap.put(pa,paSize+pbSize);
                    //pb家族从此除根
                    sizeMap.remove(pb);
                }
            }
            //找哪个家族最庞大 孩子最多 基本就是一map遍历过程
            Iterator<Map.Entry<Integer, Integer>> it = sizeMap.entrySet().iterator();
            int res=1;
            while (it.hasNext()){
                res=Math.max(res,it.next().getValue());
            }
            System.out.println(res);

        }
    }

    //找爹的函数 这里必须扁平化 否则时间过不了
    //解释一下扁平化 就是说1是2爹 2是3爹
    //这样3要找爹的话 肯定3->2  2->1 分两步
    //如果链子很长就不行了 所以现在要乱辈 大家都认一个最大是爹 剩下都是孩子
    //可以想象优化后就是一个N叉树 就两层的 根节点是爹 剩下一排孩子
    private static int find(Map<Integer, Integer> parent, int i) {
        //保存沿途想认最大的爹为爹的孩子节点
        Stack<Integer> s=new Stack<>();
        //循环 只要我还能找到爹 就继续往下找
        while (parent.containsKey(i)){
            s.push(i);
            i=parent.get(i);
        }
        //扁平化
        while (!s.isEmpty()){
            parent.put(s.pop(),i);
        }
        //返回家族最大的爹
        return i;
    }
}

简单并查集模型

#include <iostream>

const int M = 2000010,N = 100010;

using namespace std;
int t;
int p[N];
int sum[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d",&t);

    while(t--)
    {
        int n;
        scanf("%d",&n);

        for(int i = 1;i <= N;i++)
        {
            p[i] = i;
            sum[i] = 1;
        }

        int res = 0;
        while(n--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int px = find(x),py = find(y);
            if(px != py)
            {
                 p[px] = py;
                sum[py] += sum[px];
            }


            res = max(res,sum[py]);
        }
        printf("%d\n",res);
    }

    return 0;
}

用了并查集模板就是舒服

import java.util.*;

public class Main{
    static int N = 100010; // 习惯了超出10个
    static int[] p = new int[N + 1]; // 每个用户的父节点
    static int[] size = new int[N + 1]; // 只保证根节点的数量正确有效即可

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int k = 0; k < T; k++) {
            // 每次都初始化所有用户（因为题目给了 T 组测试数据）
            for (int i = 1; i <= N; i++) {
                p[i] = i;
                size[i] = 1;
            }
            int n = sc.nextInt();
            // n对关系
            for (int i = 0; i < n; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                if(find(x) == find(y)) continue; // 不能重复挂
                // x挂到y上 之前，先统计x、y两个集合人数，再把x挂到y
                size[find(y)] += size[find(x)]; //先统计两个集合点数
                p[find(x)] = find(y); // 把x挂到y的根节点上
            }

            // 统计那个最大朋友圈的用户数
            int res = 0;
            for (int i : size) {
                res = Math.max(res, i);
            }
            System.out.println(res);
        }
    }

    // 找出x的根节点（带路径压缩）
    public static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

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

unordered_map<int, int>fa;
unordered_map<int, int>cnt;

int find(int x){
    if(fa.find(x)==fa.end()){
        fa[x]=x;
        cnt[x]=0;
    }
    if(x==fa[x]){
        return x;
    }
    return fa[x]=find(fa[x]);
}
void Union(int x,int y){
    int fx=find(x);
    int fy=find(y);
    fa[fx]=fy;
}
int main(){
    int T;cin>>T;
    while(T-- >0){
        int n;cin>>n;
        while(n-- >0){
            int x,y;
            cin>>x>>y;
            Union(x,y);
        }
        int ans=0;
        for(unordered_map<int, int>::iterator it=fa.begin();it!=fa.end();it++){
            int fi=find(it->second);
            cnt[fi]++;
            ans=max(ans,cnt[fi]);
        }
        cout<<ans<<endl;
        fa.clear();
        cnt.clear();
    }
}

using namespace std;
#include<iostream>
#include<algorithm>
#include<numeric>
#include<vector>
//#include<bits/stdc++.h>

vector<int>id(100001, 0);
vector<int>counts(100001, 1);
int maxrs = 0;
int find(int x) {     while (x!=id[x])     {         id[x] = id[id[x]];         x = id[x];     }     return x;
}

void unionxy(int x, int y) {     x = find(x);     y = find(y);     if (x != y) {         if (counts[x] > counts[y]) {             counts[x] += counts[y];             counts[y] = 0;             id[y] = id[x];             if (maxrs < counts[x])                 maxrs = counts[x];         }         else {             counts[y] += counts[x];             counts[x] = 0;             id[x] = id[y];             if (maxrs < counts[y])                 maxrs = counts[y];         }     }      }

int main() {     int T;     cin >> T;          while (T--)     {             int n;         cin >> n;         iota(id.begin(), id.end(), 0);         fill(counts.begin(), counts.end(), 1);         maxrs = 0;         for (int i = 0; i < n; i++) {             int x, y;             cin >> x >> y;             unionxy(x, y);         }         cout << maxrs << endl;     }     return 0;
}