首页 > 试题广场 >

城市群数量

[编程题]城市群数量
  • 热度指数:1302 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个 n 个节点的邻接矩阵 m。 节点定义为城市,如果 a 城市与 b 城市相连, b 与 c 城市相连,尽管 a 与 c 并不直接相连,但可以认为 a 与 c 相连,定义 a,b,c 是一个城市群。
矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,否则表示不相连。
请你找出共有多少个城市群。

数据范围: , 矩阵中只包含
示例1

输入

[[1,1,0],[1,1,0],[0,0,1]]

输出

2

说明

1 2 相连,3 独立,因此是 3 个城市群。 
示例2

输入

[[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]

输出

2

说明

1 , 2相连 ;2 ,3相连,4独立,因此是 1,2,3 属于一个城市群,4属于一个城市群。 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param m int整型vector<vector<>> 
     * @return int整型
     */
     vector<int>f;

     int find(int x){
        if(this->f[x]==x)return x;
        else return this->f[x]=find(this->f[x]);
     }

     void merge(int a,int b){
        int x=find(a);
        int y =find(b);
        this->f[x]=y;

     }

    int citys(vector<vector<int> >& m) {
        // write code here
        // 初始化
        this->f=vector<int>(m.size());
        int n=m.size();
        for(int i=0;i<n;i++){
            this->f[i]=i;
        }
        // 合并相连城市
        for(int i=0;i<n;i++){
            for(int j=0;j<m[i].size();j++){
                if(m[i][j]==1){
                    merge(i,j);
                }
            }
        }

        //通过unordered_set统计城市群数量 
        int cntFather=0;
        unordered_set<int >st;
        for(int i=0;i<n;i++){
            st.insert(find(i));
        }
        cntFather=st.size();
        return cntFather;

    }
};

发表于 2024-02-01 09:13:03 回复(0)
这道题是不是答案有问题呀,怎么是3?
发表于 2023-10-15 21:43:24 回复(0)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param m int整型二维数组 
 * @param mRowLen int m数组行数
 * @param mColLen int* m数组列数
 * @return int整型
 */
void dfs(int** m, int mr, int mc,int i){

    for(int j=0;j<mr;j++){
        if(m[i][j]==1){
            m[i][j]=0;
             m[j][i]=0;
           dfs(m,mr,mc,j);
           }
    }
      
}
int citys(int** m, int mRowLen, int* mColLen ) {
    // write code here
    int count=0;
    for(int i=0;i<mRowLen;i++){
        for(int j=0;j<*mColLen;j++){
            
                if(m[i][j]==1){
                    count++;
                    m[i][j]=0;
                    m[j][i]=0;
                    dfs(m,mRowLen,*mColLen,i);
                    dfs(m,mRowLen,*mColLen,j);

                
            }
        }
    }
    return count;
}

发表于 2023-01-10 16:24:11 回复(0)
class Solution:
    map=[]
    def citys(self , m: List[List[int]]) -> int:
        num=0
        self.map=[0]*len(m)
        for i in range(len(m)):
            if self.map[i]==0:
                num+=1
                self.dfs(i,m)
        return num

    def dfs(self,x,m):
        self.map[x]=1
        for i in range(len(m[x])):
            if m[x][i]==1 and self.map[i]==0:
                self.dfs(i,m)

发表于 2022-09-24 16:49:28 回复(0)
# python3
# 并查集做法
# 总城市肯定是m
# 每有两个城市互相连接,数量就减1 

class Solution:
    def __init__(self):
        self.n = 210 
        self.father = [i for i in range(self.n)]
    def find(self, u):
        if u == self.father[u]:
            return u
        self.father[u] = self.find(self.father[u])
        return self.father[u]
    
    def same(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return True 
        return False 
    
    def join(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return 
        self.father[u] = v
        pass     
    def citys(self , m: List[List[int]]) -> int:
        # write code here
        cnt = len(m)
        for i in range(len(m)):
            for j in range(len(m[0])):
                if m[i][j] == 1:
                    if not self.same(i, j):
                        self.join(i, j)
                        cnt -= 1
                    else:
                        continue
        return cnt 

发表于 2022-08-15 05:56:19 回复(0)
并查集做法,时间复杂度O(n2),具体代码如下
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();
    }
};


发表于 2022-05-14 10:35:45 回复(0)
public class Solution {
    // dfs遍历邻接矩阵就可以
    public int citys (ArrayList<ArrayList<Integer>> matrix) {
        int m = matrix.size();
        v = new boolean[m];
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (!v[i]) {
                cnt++;
                dfs(i, matrix, m);
            }  
        }
        return cnt;
    }
    boolean[] v;
    public void dfs(int i, ArrayList<ArrayList<Integer>> matrix, int m) {
        if (!v[i]) {
            v[i] = true;
            for (int j = 0; j < m; j++) {
                if (matrix.get(i).get(j) == 1) {
                    dfs(j, matrix, m);
                }
            }
        }
    }
}
发表于 2022-05-07 12:45:21 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param m int整型ArrayList<ArrayList<>> 
     * @return int整型
     */
    public int citys (ArrayList<ArrayList<Integer>> m) {
        // write code here
        int n = m.size();
        int k = m.get(0).size();
//         int[][] arr = new int[n][k];
        
        int[] visited = new int[n];
        int ans = 0;
        for(int i = 0;i<n;i++){
//             System.out.println(i);
            if(visited[i] == 0){
                ans++;
                dfs(m,visited,i);
            }
        }
        return ans;
    }
    
    public void dfs(ArrayList<ArrayList<Integer>> m,int[] visited,int node){
        visited[node] = 1;
        ArrayList<Integer> arr = m.get(node);
        for(int i = 0;i<arr.size();i++){
            if(arr.get(i)!=0 && visited[i] == 0){
                dfs(m,visited,i);
            }
        }
    }
}

发表于 2022-03-21 12:00:38 回复(0)

问题信息

难度:
8条回答 2928浏览

热门推荐

通过挑战的用户

查看代码