【数组】B_1267. 统计参与通信的服务器（枚举 / 并查集）

一、题目描述

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4

二、题解

方法一：枚举

• 同一行和同一列必须要有两台或以上的计算机才能互相通信。
• 也就是说某一个位置所在行和列只有一台 PC 的话，是无法互相通信的。

public int countServers(int[][] grid) {
    int R = grid.length, C = grid[0].length;
    int[] row = new int[R];
    int[] col = new int[C];
    int res = 0;
    for (int x = 0; x < R; x++) 
    for (int y = 0; y < C; y++) {
        if (grid[x][y] == 1) {
            row[x]++; col[y]++;
            res++;
        }
    }
    for (int x = 0; x < R; x++) 
    for (int y = 0; y < C; y++) {
        if (grid[x][y] == 1 && row[x] == 1 && col[y] == 1) {
            res--;
        }
    }
    return res;
}

复杂度分析

• 时间复杂度：$O(R × C)$O(R×C)，
• 空间复杂度：$O(R × C)$O(R×C)，

---

方法二：并查集

• 如果遇到某一个格子是 1，那么就合并其所在行和列，并且 count++。
• 最后，在并查集 uf 中查找某一个结点下只有一个孩子，如果有，证明这个 pc 是独立的，count--。

Q&A

• Q1：为什么合并行和列是 union(i, j+row)？
  A1，错误解释：矩形有 m 行，n 列，但并查集的 id 数组只有一行，故 $0, ... , m, m+1 , ..., m+n-1$0,...,m,m+1,...,m+n−1 表示示 id 数组的值，故此处 j + m 表示 i 行 j 列在 id 数组中的索引。

int R, C;
public int countServers(int[][] grid) {
    R = grid.length; C = grid[0].length;
    int tot = 0;
    UF uf = new UF(R + C);
    for (int i = 0; i < R; i++)
    for (int j = 0; j < C; j++) {
        if (grid[i][j] == 1) {
            tot++;
            uf.union(i, j+R);
        }
    }
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < R; i++)
    for (int j = 0; j < C; j++) {
        if (grid[i][j] == 1) {
            int p = uf.find(i);
            map.put(p, map.getOrDefault(p, 0)+1);
        }
    }
    for (int k : map.keySet()) {
        if (map.get(k) == 1)
            tot--;
    }
    return tot;
}

class UF {
    int[] id;
    int count;
    
    public UF(int N) {
        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
    }
    public int find(int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }
    public boolean isConn(int p, int q) {
        return find(p) == find(q);
    }
    public void union(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if (pID == qID) {
            return;
        }
        id[pID] = qID;
        count--;
    }
}

复杂度分析

• 时间复杂度：$O()$O()，
• 空间复杂度：$O()$O()，