4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

3
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 读取矩阵的大小
        int[][] matrix = new int[n][n];  // 创建邻接矩阵

        // 读取邻接矩阵的内容
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();  // 填充矩阵
            }
        }

        // 调用函数，计算并输出最大的连通分量大小
        System.out.println(findMaxCluster(matrix, n));
    }

    // 计算最大连通分量的大小
    public static int findMaxCluster(int[][] matrix, int n) {
        boolean[] visited = new boolean[n];  // 记录节点是否被访问过
        int maxSize = 0;  // 最大连通分量的大小

        // 遍历所有节点，找到每个未访问的节点并开始DFS
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {  // 如果节点未被访问过
                int size = dfs(matrix, visited, i, n);  // 深度优先搜索，获取连通分量的大小
                maxSize = Math.max(maxSize, size);  // 更新最大连通分量的大小
            }
        }

        return maxSize;  // 返回最大的连通分量大小
    }

    // 深度优先搜索 (DFS) 计算当前连通分量的大小
    private static int dfs(int[][] matrix, boolean[] visited, int i, int n) {
        visited[i] = true;  // 标记当前节点为已访问
        int size = 1;  // 当前连通分量的大小，初始为1（当前节点）

        // 遍历与当前节点 i 相连的所有节点
        for (int j = 0; j < n; j++) {
            // 如果矩阵[i][j] == 1 且 j 节点没有被访问过，则递归访问 j
            if (matrix[i][j] == 1 && !visited[j]) {
                size += dfs(matrix, visited, j, n);  // 递归DFS，增加连通分量大小
            }
        }

        return size;  // 返回当前连通分量的大小
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

• 1

JS解法

• 解题思路

• 问题理解：

给定一个图的邻接矩阵，我们需要找出图中最大的连通分量的大小。每个节点可以通过边与其他节点相连，连通分量是指一组相互连接的节点。
并查集算法：

使用并查集（Union-Find）算法来解决连通分量的合并与查找问题。并查集是一种高效的数据结构，可以用于解决动态连通性问题。在这个问题中，我们将图中的节点作为并查集的元素，边作为并查集的连接操作。
算法步骤：

初始化并查集：每个节点的父节点初始化为自身。
遍历邻接矩阵：通过双重循环检查所有的边。如果两个节点之间有边，就将它们合并在一起。
统计每个连通分量的大小：通过并查集的 find 操作找到每个节点的根节点，并计算不同根节点的连通分量大小。
返回最大连通分量的大小。
时间复杂度：

由于每个合并和查找操作的时间复杂度是接近常数的（通过路径压缩和按秩合并优化），所以总体时间复杂度为 O(n^2)，其中 n 是节点的数量。

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let graphSize;
const inputLines = [];

// 监听输入
rl.on("line", (line) => {
    inputLines.push(line);  // 将每行输入保存到数组中
    if (inputLines.length === 1) {
        graphSize = Number(inputLines[0]);  // 第一行是图的大小n
    }

    // 读取完图的邻接矩阵数据后处理
    if (graphSize && inputLines.length === graphSize + 1) {
        inputLines.shift(); // 去掉第一行的图大小
        const adjacencyMatrix = parseInput(inputLines);  // 解析邻接矩阵
        const result = findLargestComponent(adjacencyMatrix);  // 查找最大连通分量
        console.log(result);  // 输出结果
        inputLines.length = 0; // 重置输入行数组
    }
});

// 解析输入，生成邻接矩阵
function parseInput(lines) {
    return lines.map((line) => line.split(" ").map(Number));  // 将每行的字符串转换为数字数组
}

// 查找图中最大的连通分量
function findLargestComponent(matrix) {
    const unionFind = new UnionFind(matrix.length);  // 初始化并查集

    // 遍历邻接矩阵中的每一条边
    for (let i = 0; i < matrix.length; i++) {
        for (let j = i + 1; j < matrix.length; j++) {
            if (matrix[i][j] === 1) {  // 如果i和j之间有边
                unionFind.union(i, j);  // 将i和j合并到同一个连通分量中
            }
        }
    }

    // 统计每个连通分量的大小
    const componentSize = {};
    for (let i = 0; i < matrix.length; i++) {
        const root = unionFind.find(unionFind.fa[i]);  // 查找当前节点的根节点
        componentSize[root] = (componentSize[root] || 0) + 1;  // 根据根节点统计连通分量大小
    }

    // 返回最大的连通分量的大小
    return Math.max(...Object.values(componentSize));
}

// 并查集类
class UnionFind {
    constructor(size) {
        this.fa = Array.from({ length: size }, (_, i) => i);  // 初始化父节点数组，每个节点的父节点为其自身
        this.count = size;  // 连通分量的数量
    }

    // 查找操作，带路径压缩优化
    find(x) {
        if (x !== this.fa[x]) {
            this.fa[x] = this.find(this.fa[x]);  // 递归查找根节点，同时压缩路径
        }
        return this.fa[x];  // 返回根节点
    }

    // 合并操作，将x和y所在的连通分量合并
    union(x, y) {
        const rootX = this.find(x);  // 查找x的根节点
        const rootY = this.find(y);  // 查找y的根节点

        if (rootX !== rootY) {
            this.fa[rootY] = rootX;  // 将y的根节点指向x的根节点
            this.count--;  // 连通分量数减少
        }
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

发表评论

登录后才能发表评论和回复 注册

/ 登录

提交评论

评论记录：

未查询到任何数据！

回复评论：

×

关闭 提交评论