城市群数量

C++ 解法, 执行用时: 6ms, 内存消耗: 776KB, 提交时间: 2022-05-18

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param m int整型vector<vector<>> 
     * @return int整型
     */
    vector<int> num;
    int parent[200*200];
    int cnt = 0;
    int Find(int x){
        int root = x;
        while(root!=parent[root]){
            root = parent[root];
        }
        while(x!=parent[x]){
            int tmp = parent[x];
            parent[x] = root;
            x = tmp;
        }
        return root;
    }
    void Union(int x, int y){
        int proot = Find(x);
        int qroot = Find(y);
        if(proot==qroot)
            return;
        parent[proot] = qroot;
        cnt--;
    }
    int citys(vector<vector<int> >& m) {
        // write code here
        int n = m.size();
        cnt = n;
        if(n<=0)
            return 0;
        for(int i=0;i<n;i++)
            parent[i] = i;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(m[i][j]==1 && i!=j)
                    Union(i, j);
            }
        }
        return cnt;
    }
};

C++ 解法, 执行用时: 6ms, 内存消耗: 776KB, 提交时间: 2022-05-15

class UF {
public:
    UF() = default;
    UF(int n) {
        cnt = n;
        parent.resize(n);

        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    void ufUnion(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) return;

        parent[pRoot] = qRoot;
        cnt--;
    }

    bool isConnected(int p, int q) {
        return find(p) == find(q);
    }

    int count() {
        return cnt;
    }

private:
    int cnt;
    vector<int> parent;
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param m int整型vector<vector<>>
     * @return int整型
     */
    int citys(vector<vector<int> >& m) {
        // write code here
        int n = m.size();
        UF uf(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (m[i][j] == 1)
                    uf.ufUnion(i, j);
            }
        }
        
        return uf.count();
    }
};

C++ 解法, 执行用时: 6ms, 内存消耗: 780KB, 提交时间: 2022-04-11

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param m int整型vector<vector<>> 
     * @return int整型
     */
    int *fa;
    int citys(vector<vector<int> >& m) {
        // write code here
        int n = m.size();
        
        Init(m);
        
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(m[i][j] == 1)
                {
                    Merge(i,j);
                }
            }
        }
        
        int res = 0;
        for(int i = 0; i < n; i++)
        {
            if(fa[i] == i)
            {
                res++;
            }
        }
        return res;
    }
    
    void Init(vector<vector<int> >& m)
    {
        int n = m.size();
        fa = new int[n];
        for(int i = 0; i < n; i++)
        {
            fa[i] = i;
        }
    }
    
    int Find(int i)
    {
        if(fa[i] == i)
        {
            return i;
        }
        else
        {
            fa[i] = Find(fa[i]);
            return fa[i];
        }
    }
    
    void Merge(int i, int j)
    {
        int a_i = Find(i);
        int a_j = Find(j);
        fa[a_i] = a_j;
    }
};

C 解法, 执行用时: 7ms, 内存消耗: 660KB, 提交时间: 2022-06-27

void dfs(int** m, int i, int colLen, int* a) {
    a[i] = 1;
    for (int j = 0; j < colLen; j++) {
        if (m[i][j] == 1 && a[j] == 0) {dfs(m, j, colLen, a);}
    }
}
int citys(int** m, int mRowLen, int* mColLen ) {
    int a[mRowLen];
    memset(a, 0, sizeof(a));
    int sum = 0;
    for (int i = 0; i < mRowLen; i++) {
        if (a[i] == 0) {
            sum++;
            dfs(m, i, *mColLen, a);
        }
    }
    return sum;
}

C 解法, 执行用时: 7ms, 内存消耗: 740KB, 提交时间: 2022-06-26

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param m int整型二维数组 
 * @param mRowLen int m数组行数
 * @param mColLen int* m数组列数
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
void dfs(int** m, int i, int colLen, int *visited) {
    visited[i] = 1;
    
    for (int j = 0; j < colLen; j++) {
        if (m[i][j] == 1 && visited[j] == 0) {
            dfs(m, j, colLen, visited);
        }
    }
}

int citys(int** m, int mRowLen, int* mColLen ) {
    int visited[mRowLen];
    memset(visited, 0, sizeof(visited));
    int mapCount = 0;
    
    for (int i = 0; i < mRowLen; i++) {
        if (visited[i] == 0) {
            mapCount++;
            dfs(m, i, *mColLen, visited);
        }
    }
    
    return mapCount;
}

详情