给定一个 n 个节点的邻接矩阵 m。 节点定义为城市，如果 a 城市与 b 城市相连， b 与 c 城市相连，尽管 a 与 c 并不直接相连，但可以认为 a 与 c 相连，定义 a,b,c 是一个城市群。
矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，否则表示不相连。
请你找出共有多少个城市群。
数据范围： 
， 矩阵中只包含
和
[编程题]城市群数量
import java.util.*;
/**
* NC345 城市群数量
* @author d3y1
*/
public class Solution {
private int result = 0;
private int N;
private boolean[] isVisited;
private HashSet<Integer>[] adj;
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param m int整型ArrayList<ArrayList<>>
* @return int整型
*/
public int citys (ArrayList<ArrayList<Integer>> m) {
// return solution1(m);
// return solution2(m);
return solution3(m);
}
/**
* dfs
* @param m
* @return
*/
private int solution1(ArrayList<ArrayList<Integer>> m){
N = m.size();
isVisited = new boolean[N];
adj = new HashSet[N];
for(int i = 0; i < N; i++){
adj[i] = new HashSet<>();
}
for(int i = 0; i < N; i++){
for(int j = i+1; j < N; j++){
if(m.get(i).get(j) == 1){
adj[i].add(j);
adj[j].add(i);
}
}
}
for(int i = 0; i < N; i++){
if(!isVisited[i]){
dfs(i);
result++;
}
}
return result;
}
/**
* 递归
* @param city
*/
private void dfs(int city){
if(isVisited[city]){
return;
}
isVisited[city] = true;
for(int adjCity: adj[city]){
dfs(adjCity);
}
}
/**
* bfs
* @param m
* @return
*/
private int solution2(ArrayList<ArrayList<Integer>> m){
N = m.size();
isVisited = new boolean[N];
adj = new HashSet[N];
for(int i = 0; i < N; i++){
adj[i] = new HashSet<>();
}
for(int i = 0; i < N; i++){
for(int j = i+1; j < N; j++){
if(m.get(i).get(j) == 1){
adj[i].add(j);
adj[j].add(i);
}
}
}
for(int i = 0; i < N; i++){
if(!isVisited[i]){
bfs(i);
result++;
}
}
return result;
}
/**
* 非递归: 队列
* @param city
*/
private void bfs(int city){
Queue<Integer> queue = new LinkedList<>();
queue.offer(city);
int currCity;
while(!queue.isEmpty()){
currCity = queue.poll();
isVisited[currCity] = true;
for(int adjCity: adj[currCity]){
if(!isVisited[adjCity]){
queue.offer(adjCity);
}
}
}
}
/**
* 并查集
* @param m
* @return
*/
private int solution3(ArrayList<ArrayList<Integer>> m){
int n = m.size();
UnionFind uf = new UnionFind(n);
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
if(m.get(i).get(j) == 1){
uf.union(i,j);
}
}
}
return uf.connects();
}
/**
* 并查集类
*/
private class UnionFind {
int connect;
int[] parent;
UnionFind(int n){
this.connect = n;
parent = new int[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 union(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP != rootQ){
parent[rootP] = rootQ;
this.connect--;
}
}
int connects(){
return this.connect;
}
}
}
发表于 2025-02-23 12:29:17
回复(0)
并查集常规题，熟练一遍模板
class Solution:
def citys(self , m: List[List[int]]) -> int:
n = len(m)
arr = [0] * n
for i in range(n):
arr[i] = i
def find(i):
if arr[i] == i:
return i
arr[i] = find(arr[i])
return arr[i]
def union(i, j):
arr[find(i)] = find(j)
for i in range(1, n):
for j in range(i):
if m[i][j] == 1:
union(i, j)
ret = 0
for i in range(n):
if i == arr[i]:
ret += 1
return ret public class Solution {
int[] arr;
public int citys (ArrayList<ArrayList<Integer>> m) {
// write code here
int n = m.size();
arr = new int[n];
for (int i = 0; i < n; ++i)
arr[i] = i;
for (int i = 1; i < n; ++i)
for (int j = 0; j < i; ++j)
if (m.get(i).get(j) == 1)
union(i, j);
int ret = 0;
for (int i = 0; i < n; ++i)
if (arr[i] == i)
ret++;
return ret;
}
private int find(int i) {
if (i == arr[i])
return i;
arr[i] = find(arr[i]);
return arr[i];
}
private void union(int i, int j) {
arr[find(i)] = find(j);
}
}
发表于 2024-07-25 15:37:16
回复(0)
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)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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)
问题信息
难度：
10条回答
33收藏
6733浏览
通过挑战的用户
查看代码-
2022-09-14 23:55:07 -
2022-09-14 17:54:41 -
2022-09-13 19:21:36 -
2022-09-12 15:07:15
-
2022-09-10 16:11:58
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
