原文链接: https://leetcode-cn.com/problems/bLyHh0

中文题目

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

 

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

 

提示：

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] 为 1 或 0
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

 

注意：本题与主站 547 题相同： https://leetcode-cn.com/problems/number-of-provinces/

通过代码

高赞题解

思路和心得：

（一）dfs

[]
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(x: int) -> None:
            # nonlocal visited
            for y in range(n):
                if visited[y] == False and isConnected[x][y] == 1:
                    visited[y] = True
                    dfs(y)
        
        n = len(isConnected)
        visited = [False for _ in range(n)]
        cnt = 0
        for x in range(n):
            if visited[x] == False:
                visited[x] = True
                dfs(x)
                cnt += 1
        return cnt 

[]
class Solution 
{
public:
    vector<vector<int>> isConnected;
    int n;
    vector<bool> visited;
    int cnt;

    int findCircleNum(vector<vector<int>>& isConnected) 
    {
        this->isConnected = isConnected;
        this->n = (int)isConnected.size();
        this->visited.resize(n, false);

        for (int x = 0; x < n; x ++)
        {
            if (visited[x] == false)
            {
                visited[x] = true;
                dfs(x);
                cnt ++;
            }
        }
        return cnt;
    }

    void dfs(int x)
    {
        for (int y = 0; y < n; y ++)
        {
            if (isConnected[x][y] == 1 && visited[y] == false)
            {
                visited[y] = true;
                dfs(y);
            }
        }
    }
};

[]
class Solution 
{
    int [][] isConnected;
    int n;
    boolean [] visited;
    int cnt = 0;

    public int findCircleNum(int[][] isConnected) 
    {
        this.isConnected = isConnected;
        this.n = isConnected.length;
        visited = new boolean[n];
        for (int x = 0; x < n; x ++)
        {
            if (visited[x] == false)
            {
                visited[x] = true;
                bfs(x);
                cnt ++;
            }
        }
        return cnt;
    }

    public void dfs(int x)
    {
        for (int y = 0; y < n; y ++)
        {
            if (isConnected[x][y] == 1 && visited[y] == false)
            {
                visited[y] = true;
                dfs(y);
            }
        }
    }
}

（二）bfs

[]
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def bfs(sx: int) -> None:
            q = collections.deque()
            q.append(sx)
            while q:
                x = q.popleft()
                for y in range(n):
                    if visited[y] == False and isConnected[x][y] == 1:
                        visited[y] = True
                        q.append(y)
        
        n = len(isConnected)
        visited = [False for _ in range(n)]
        cnt = 0
        for x in range(n):
            if visited[x] == False:
                visited[x] = True
                bfs(x)
                cnt += 1
        return cnt

[]
class Solution 
{
public:
    vector<vector<int>> isConnected;
    int n;
    vector<bool> visited;
    int cnt;

    int findCircleNum(vector<vector<int>>& isConnected) 
    {
        this->isConnected = isConnected;
        this->n = (int)isConnected.size();
        this->visited.resize(n, false);

        for (int x = 0; x < n; x ++)
        {
            if (visited[x] == false)
            {
                visited[x] = true;
                bfs(x);
                cnt ++;
            }
        }
        return cnt;
    }

    void bfs(int sx)
    {
        queue<int> q;
        q.push(sx);
        while(!q.empty())
        {
            int x = q.front();    q.pop();
            for (int y = 0; y < n; y ++)
            {
                if (isConnected[x][y] == 1 && visited[y] == false)
                {
                    visited[y] = true;
                    q.push(y);
                }
            }
        }

    }
};

[]
class Solution 
{
    int [][] isConnected;
    int n;
    boolean [] visited;
    int cnt = 0;

    public int findCircleNum(int[][] isConnected) 
    {
        this.isConnected = isConnected;
        this.n = isConnected.length;
        visited = new boolean[n];
        for (int x = 0; x < n; x ++)
        {
            if (visited[x] == false)
            {
                visited[x] = true;
                bfs(x);
                cnt ++;
            }
        }
        return cnt;
    }

    public void bfs(int sx)
    {
        Queue<Integer> q = new LinkedList<>();
        q.offer(sx);
        while (!q.isEmpty())
        {
            int x = q.poll();
            for (int y = 0; y < n; y ++)
            {
                if (isConnected[x][y] == 1 && visited[y] == false)
                {
                    visited[y] = true;
                    q.offer(y);
                }
            }
        }
    }
}

（三）并查集

[]
class UnionFind:
    def __init__(self, n: int):
        self.parent = [x for x in range(n)]
        self.size = [1 for x in range(n)]
        self.part = n

    def Find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.Find(self.parent[x])
        return self.parent[x]
    
    def Union(self, x: int, y: int) -> bool:
        root_x = self.Find(x)
        root_y = self.Find(y)
        if root_x == root_y:
            return False
        if self.size[root_x] > self.size[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] = root_y
        self.size[root_y] += self.size[root_x]
        self.part -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.Find(x) == self.Find(y)
        

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        UF = UnionFind(n)
        for x in range(n):
            for y in range(n):
                if isConnected[x][y] == 1:
                    UF.Union(x, y)
        return UF.part

[]
class UnionFind
{
public:
    vector<int> parent;
    vector<int> size;
    int part;

    UnionFind(int n)
    {
        parent.resize(n);
        for (int x = 0; x < n; x ++)
            parent[x] = x;
        size.resize(n, 1);
        part = n;
    }

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

    bool Union(int x, int y)
    {
        int root_x = Find(x);
        int root_y = Find(y);
        if (root_x == root_y)
            return false;
        if (size[root_x] > root_y)
            swap(root_x, root_y);
        parent[root_x] = root_y;
        size[root_y] += size[root_x];
        part --;
        return true;
    }

    bool connected(int x, int y)
    {
        return Find(x) == Find(y);
    }

};

class Solution 
{
public:
    int findCircleNum(vector<vector<int>>& isConnected) 
    {
        int n = isConnected.size();
        UnionFind UF = UnionFind(n);
        for (int x = 0; x < n; x ++)
        {
            for (int y = 0; y < n; y ++)
            {
                if (isConnected[x][y] == 1)
                {
                    UF.Union(x, y);
                }
            }
        }

        return UF.part;
    }
};

[]
class UnionFind
{
    public int [] parent;
    public int [] size;
    public int part;

    UnionFind(int n)
    {
        parent = new int [n];
        for (int x = 0; x < n; x ++)
            parent[x] = x;
        size = new int [n];
        for (int x = 0; x < n; x ++)
            size[x] = 1;
        part = n;
    }

    public int Find(int x)
    {
        if (parent[x] != x)
            parent[x] = Find(parent[x]);
        return parent[x];
    }

    public boolean Union(int x, int y)
    {
        int root_x = Find(x);
        int root_y = Find(y);
        if (root_x == root_y)
            return false;
        if (size[root_x] > size[root_y])
        {
            int tmp = root_x;
            root_x = root_y;
            root_y = tmp;
        }
        parent[root_x] = root_y;
        size[root_y] += size[root_x];
        part --;
        return true;
    }

    public boolean connected(int x, int y)
    {
        return Find(x) == Find(y);
    }

}


class Solution 
{
    public int findCircleNum(int[][] isConnected) 
    {
        int n = isConnected.length;
        UnionFind UF = new UnionFind(n);
        for (int x = 0; x < n; x ++)
        {
            for (int y = 0; y < n; y ++)
            {
                if (isConnected[x][y] == 1)
                {
                    UF.Union(x, y);
                }
            }
        }

        return UF.part;
    }
}

统计信息

通过次数	提交次数	AC比率
4780	7375	64.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言