Đề bài
In a directed graph with nodes 0..n−1, a strongly connected component is a maximal group of nodes where every node can reach every other. Count the components (Kosaraju's or Tarjan's algorithm).
Implement count_scc(n, edges).
Input
n: The number of nodes. edges: Directed edges as [from, to].
Output
Return the number of components.
Ràng buộc
1 ≤ n ≤ 100,000; 0 ≤ edges ≤ 200,000
Ví dụ
Đầu vào:
n = 5
edges = [
[0, 1],
[1, 2],
[2, 0],
[3, 4]
]
Kết quả mong đợi:
expected = 3Đầu vào:
long long n = 5;
std::vector<std::vector<long long>> edges = {
{0, 1},
{1, 2},
{2, 0},
{3, 4}
};
Kết quả mong đợi:
long long expected = 3;Đầu vào:
long n = 5;
long[][] edges = new long[][] {
new long[] {0, 1},
new long[] {1, 2},
new long[] {2, 0},
new long[] {3, 4}
};
Kết quả mong đợi:
long expected = 3;Giải thích
0, 1, 2 form a cycle (one component); 3 and 4 can't reach each other, so they are separate: 3.
Đầu vào:
n = 3
edges = [
[0, 1],
[1, 0],
[1, 2],
[2, 1]
]
Kết quả mong đợi:
expected = 1Đầu vào:
long long n = 3;
std::vector<std::vector<long long>> edges = {
{0, 1},
{1, 0},
{1, 2},
{2, 1}
};
Kết quả mong đợi:
long long expected = 1;Đầu vào:
long n = 3;
long[][] edges = new long[][] {
new long[] {0, 1},
new long[] {1, 0},
new long[] {1, 2},
new long[] {2, 1}
};
Kết quả mong đợi:
long expected = 1;Giải thích
All three nodes reach each other: 1.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Một đỉnh chỉ cùng thành phần với đỉnh khác nếu mỗi đỉnh đều đi tới được đỉnh kia, nên hãy nghĩ về các vùng liên thông mạnh thay vì chỉ độ với tới đơn giản.
Gợi ý 2
Duyệt đồ thị gốc theo một thứ tự, rồi duyệt đồ thị đảo để gom từng vùng một.
Gợi ý 3
Chú ý thứ tự kết thúc và các đỉnh cô lập; mọi đỉnh phải được gán đúng một lần, kể cả khi không có cạnh vào hay ra.
Độ phức tạp mong đợi
thời gian O(n + m), bộ nhớ phụ O(n + m)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.