# BFS
from collections import deque

n = int(input())
isConnected = list()
for _ in range(n):
    isConnected.append(list(map(int, input().split())))

ans = 0
checkList = [0] * n     # 构建检查数组checkList

# 遍历每一个版本
for i in range(n):
    if checkList[i] == 0:       # 若版本i未检查过
        q = deque([i])          # 把版本i加入q中，作为BFS的起始位置
        checkList[i] = 1        # 将版本i标记为已检查过
        cur_num = 0             # cur_num表示本次BFS包含的版本数，初始化为0
        # 从版本i开始，进行BFS
        while(q):
            # 弹出q队头的版本x，考虑所有与其相连的版本y
            x = q.popleft()
            # 本次搜索得到的版本数目+1
            cur_num += 1
            # 对于版本x，遍历所有其他版本y，若y未检查过，且与x相连
            for y in range(n):
                if x != y and checkList[y] == 0 and isConnected[x][y] == 1:
                    q.append(y)         # 则把版本y加入队列中
                    checkList[y] = 1    # 同时把版本y标记为已检查过
        # 完成本次BFS，比较ans和cur_num，更新ans
        ans = max(ans, cur_num)

print(ans)

Java

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] isConnected = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                isConnected[i][j] = scanner.nextInt();
            }
        }

        int ans = 0;
        int[] checkList = new int[n];

        for (int i = 0; i < n; i++) {
            if (checkList[i] == 0) {
                Queue<Integer> queue = new ArrayDeque<>();
                queue.add(i);
                checkList[i] = 1;
                int curNum = 0;

                while (!queue.isEmpty()) {
                    int x = queue.poll();
                    curNum++;

                    for (int y = 0; y < n; y++) {
                        if (x != y && checkList[y] == 0 && isConnected[x][y] == 1) {
                            queue.add(y);
                            checkList[y] = 1;
                        }
                    }
                }

                ans = Math.max(ans, curNum);
            }
        }

        System.out.println(ans);
    }
}

C++

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> isConnected(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> isConnected[i][j];
        }
    }

    int ans = 0;
    vector<int> checkList(n, 0);

    for (int i = 0; i < n; i++) {
        if (checkList[i] == 0) {
            queue<int> q;
            q.push(i);
            checkList[i] = 1;
            int curNum = 0;

            while (!q.empty()) {
                int x = q.front();
                q.pop();
                curNum++;

                for (int y = 0; y < n; y++) {
                    if (x != y && checkList[y] == 0 && isConnected[x][y] == 1) {
                        q.push(y);
                        checkList[y] = 1;
                    }
                }
            }

            ans = max(ans, curNum);
        }
    }

    cout << ans << endl;
    return 0;
}

解法二：DFS

Python

# DFS
def dfs(x, isConnected, checkList):
    # 声明变量cur_num为全局变量，表示当前DFS所遍历的版本数
    global cur_num
    cur_num += 1
    # 对于传入的版本x，将其标记为已检查过
    checkList[x] = 1
    # 遍历其他版本y，若版本y未检查过，且与版本x相连
    for y in range(n):
        if y != x and checkList[y] == 0 and isConnected[x][y] == 1:
            dfs(y, isConnected, checkList)  # 则对y进行DFS

n = int(input())
isConnected = list()
for _ in range(n):
    isConnected.append(list(map(int, input().split())))

ans = 0
checkList = [0] * n         # 构建检查数组checkList

# 遍历每一个版本
for i in range(n):
    # 如果该版本没检查过，则以版本i作为起始点，进行DFS
    if checkList[i] == 0:
        # cur_num表示本次DFS包含的版本数，初始化为0
        cur_num = 0
        # 进行DFS搜索
        dfs(i, isConnected, checkList)
        # 完成本次BFS，比较ans和cur_num，更新ans
        ans = max(ans, cur_num)

print(ans)

Java

import java.util.Scanner;

public class Main {
    static int n;
    static int[][] isConnected;
    static int[] checkList;
    static int ans = 0;
    static int cur_num = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        isConnected = new int[n][n];
        checkList = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                isConnected[i][j] = scanner.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            if (checkList[i] == 0) {
                cur_num = 0;
                dfs(i);
                ans = Math.max(ans, cur_num);
            }
        }

        System.out.println(ans);
    }

    static void dfs(int x) {
        checkList[x] = 1;
        cur_num++;
        for (int y = 0; y < n; y++) {
            if (y != x && checkList[y] == 0 && isConnected[x][y] == 1) {
                dfs(y);
            }
        }
    }
}

C++

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

int n;
vector<vector<int>> isConnected;
vector<int> checkList;
int ans = 0;
int cur_num = 0;

void dfs(int x) {
    checkList[x] = 1;
    cur_num++;
    for (int y = 0; y < n; y++) {
        if (y != x && checkList[y] == 0 && isConnected[x][y] == 1) {
            dfs(y);
        }
    }
}

int main() {
    cin >> n;
    isConnected.resize(n, vector<int>(n));
    checkList.resize(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> isConnected[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        if (checkList[i] == 0) {
            cur_num = 0;
            dfs(i);
            ans = max(ans, cur_num);
        }
    }

    cout << ans << endl;
    return 0;
}

时空复杂度

时间复杂度：O(N^2)。需要遍历整个关联矩阵 isConnected。

空间复杂度：O(N)。