给定一个 n 个节点的邻接矩阵 m。 节点定义为城市,如果 a 城市与 b 城市相连, b 与 c 城市相连,尽管 a 与 c 并不直接相连,但可以认为 a 与 c 相连,定义 a,b,c 是一个城市群。
矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,否则表示不相连。
请你找出共有多少个城市群。
数据范围: , 矩阵中只包含和
[[1,1,0],[1,1,0],[0,0,1]]
2
1 2 相连,3 独立,因此是 3 个城市群。
[[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; } };
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @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; }
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)
# 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
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(); } };
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); } } } } }
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); } } } }