Có n thành phố. Một số thành phố được kết nối trực tiếp với nhau, còn một số thì không. Nếu thành phố a kết nối trực tiếp với b, và b kết nối với c, thì a kết nối gián tiếp với c.
Một tỉnh (province) là một nhóm các thành phố kết nối trực tiếp hoặc gián tiếp với nhau. Cho ma trận kề isConnected kích thước n x n. Hãy tính tổng số tỉnh.
Ví dụ 1:
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2Ví dụ 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3Định Dạng Đầu Vào (Input)
Một dòng chứa ma trận 2D isConnected
Định Dạng Đầu Ra (Output)
Một số nguyên duy nhất là số tỉnh
Ràng Buộc (Constraints)
1 <= n <= 200
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[[1,1,0],[1,1,0],[0,0,1]]
Output:
2
Giải thích: {0, 1} và {2}
Ví dụ 2:
Input:
[[1,0,0],[0,1,0],[0,0,1]]
Output:
3
Giải thích: 3 tỉnh độc lập
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Đếm Thành Phần Liên Thông O(n^2)
Duyệt qua từng thành phố từ 0 đến n-1. Nếu chưa thăm, tăng đếm số tỉnh và dùng DFS/BFS để đánh dấu toàn bộ các thành phố trong cùng tỉnh.
Dữ liệu đầu vào (Input):
[[1,1,0],[1,1,0],[0,0,1]]
Kết quả kỳ vọng (Expected Output):
2
Dữ liệu đầu vào (Input):
[[1,0,0],[0,1,0],[0,0,1]]
Kết quả kỳ vọng (Expected Output):
3
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
