Leetcode 547 - Number of Provinces

題目

Problem#

有 n 個城市，給你 nxn 的 isConnected 其中 isConnected[i][j] = 1 代表 i 和 j 相連；反之，則不相連。
province 指的是一組直接、間接相連的一群城市，問你總共有幾個 province?

測資限制#

• $1 \le n \le 200$

想法#

用 disjoint set 去維護分組，當如果城市 i 和城市 j 相連而且不在同組的話，則分到同一組。
最後去遍歷一次 disjoint set 的 p[i] 去數組長的個數

• 時間複雜度: $\mathcal{O}(n^2)$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

Copy

class Solution
{
public:
    // disjoint set
    vector<int> p;
    void init(int n)
    {
        p.resize(n);
        for(int i = 0; i < n; i++)
            p[i] = i;
    }
    int find(int x)
    {
        return p[x] == x ? x : (p[x]=find(p[x]));
    }
    void uni(int a, int b)
    {
        p[find(a)] = find(b);
    }
 
    int findCircleNum(vector<vector<int>>& G)
    {
        int n = G.size();
        init(n);
 
        for(int i = 0; i < n; i++)
        {
            for(int j = i+1; j < n; j++)
            {
                if(G[i][j] && find(i) != find(j))
                {
                    uni(i, j);
                }
            }
        }
 
        int ans = 0;
        for(int i = 0; i < n; i++)
            if(p[i] == i)
                ans++;
 
        return ans;
    }
};

view raw leetcode/547.cpp delivered with ❤ by emgithub