题目描述

Linux操作系统有多个发行版，distrowatch.com提供了各个发行版的资料。

这些发行版互相存在关联，例如Ubuntu基于Debian开发，而Mint又基于Ubuntu开发，那么我们认为Mint同Debian也存在关联。

发行版集是一个或多个相关存在关联的操作系统发行版，集合内不包含没有关联的发行版。

给你一个 $n$ * $n$ 的矩阵 $isConnected$ ，其中 $isConnected[i][j] = 1$ 表示第 $i$ 个发行版和第 $j$ 个发行版直接关联，而 $isConnected[i][j] = 0$ 表示二者不直接相连。

返回最大的发行版集中发行版的数量。

输入描述

第一行输入发行版的总数量 $N$ ，

之后每行表示各发行版间是否直接相关

输出描述

输出最大的发行版集中发行版的数量

备注

$1 ≤ N ≤ 200$

样例1

输入

4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1

输出

3

说明

$Debian(1)$ 和 $Unbuntu(2)$相关

$Mint(3)$ 和$Ubuntu(2)$相关，

$EeulerOS(4)$ 和另外三个都不相关，

所以存在两个发行版集，发行版集中发行版的数量分别是 $3$ 和 $1$ ，所以输出 $3$ 。

题面描述

给你一个 $n$ × $n$ 的矩阵 $isConnected$，其中 $isConnected[i][j] = 1$ 表示第 $i$ 个发行版和第 $j$ 个发行版直接关联，而 $isConnected[i][j] = 0$ 表示二者不直接相连。

返回最大的发行版集中发行版的数量。

思路

并查集板子题。

cpp

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

int main(){
    int N;
    cin >> N;
    // 初始化并查集，parent[i] 表示节点 i 的父节点
    vector<int> parent(N);
    for(int i=0;i<N;i++) parent[i] = i;
    
    // 查找根节点，并进行路径压缩
    function<int(int)> findSet = [&](int x) -> int{
        if(parent[x] != x){
            return parent[x] = findSet(parent[x]);
        }
        return x;
    };
    
    // 合并两个节点
    auto unionSet = [&](int x, int y) -> void{
        int fx = findSet(x);
        int fy = findSet(y);
        if(fx != fy){
            parent[fx] = fy;
        }
    };
    
    // 读取矩阵并进行合并操作
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int val;
            cin >> val;
            if(val == 1){
                unionSet(i, j);
            }
        }
    }
    
    // 统计每个根节点对应的集合大小
    map<int, int> countMap;
    for(int i=0;i<N;i++){
        int root = findSet(i);
        countMap[root]++;
    }
    
    // 找到最大的集合大小
    int maxSize = 0;
    for(auto &[k, v] : countMap){
        maxSize=max(maxSize,v);
    }
    
    cout << maxSize;
}

python

def main():
    import sys
    sys.setrecursionlimit(1000000)  # 增加递归深度以防止递归过深
    N_and_rest = sys.stdin.read().split()
    N = int(N_and_rest[0])
    matrix = []
    idx = 1
    for _ in range(N):
        row = list(map(int, N_and_rest[idx:idx+N]))
        matrix.append(row)
        idx += N

    parent = list(range(N))  # 初始化并查集，parent[i] 表示节点 i 的父节点

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # 路径压缩
        return parent[x]

    def union(x, y):
        fx = find(x)
        fy = find(y)
        if fx != fy:
            parent[fx] = fy  # 合并两个集合

    # 遍历矩阵，进行合并操作
    for i in range(N):
        for j in range(N):
            if matrix[i][j] == 1 and i != j:
                union(i, j)

    # 统计每个根节点对应的集合大小
    count_map = {}
    for i in range(N):
        root = find(i)
        if root in count_map:
            count_map[root] += 1
        else:
            count_map[root] = 1

    # 找到最大的集合大小
    max_size = max(count_map.values())
    print(max_size)

if __name__ == "__main__":
    main()

java

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

public class Main {
    // 定义并查集类
    static class UnionFind {
        int[] parent;
        public UnionFind(int size){
            parent = new int[size];
            for(int i=0;i<size;i++) parent[i] = i;
        }
        
        // 查找根节点，带路径压缩
        public int findSet(int x){
            if(parent[x] != x){
                parent[x] = findSet(parent[x]);
            }
            return parent[x];
        }
        
        // 合并两个集合
        public void unionSet(int x, int y){
            int fx = findSet(x);
            int fy = findSet(y);
            if(fx != fy){
                parent[fx] = fy;
            }
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        int[][] matrix = new int[N][N];
        for(int i=0;i<N;i++){
            String line = br.readLine().trim();
            // 处理可能的多余空格
            while(line.endsWith(" ")) {
                line = line.substring(0, line.length()-1);
            }
            String[] parts = line.split("\\s+");
            for(int j=0;j<N;j++) {
                matrix[i][j] = Integer.parseInt(parts[j]);
            }
        }
        
        // 初始化并查集
        UnionFind uf = new UnionFind(N);
        
        // 遍历矩阵，进行合并操作
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(matrix[i][j] == 1 && i != j){
                    uf.unionSet(i, j);
                }
            }
        }
        
        // 统计每个根节点对应的集合大小
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for(int i=0;i<N;i++){
            int root = uf.findSet(i);
            countMap.put(root, countMap.getOrDefault(root, 0) + 1);
        }
        
        // 找到最大的集合大小
        int maxSize = 0;
        for(int val : countMap.values()){
            if(val > maxSize) maxSize = val;
        }
        System.out.println(maxSize);  // 输出最大集合大小
    }
}