1078. Two-Edge Groups
A region has n towns numbered 0 to n-1 joined by two-way roads: edges[i] = [u, v] is a road between towns u and v. There may be several roads between the same two towns, and a road may lead from a town back to itself (such a road is useless for travel).
Two towns are safely linked if there are two routes between them that do not share any road (the routes may pass through the same towns), so closing any single road never separates them. A town is safely linked to itself. Safe links split the towns into groups, and every town lies in exactly one group; a town with no safe partner forms a group on its own.
Return the number of groups.
Example 1
- Input:
- n = 7edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,3],[2,3]]
- Output:
- 3
- Explanation:
The road 2-3 is the only link between two triangles, so the groups are {0,1,2}, {3,4,5} and the lone town 6.
Example 2
- Input:
- n = 4, edges = [[0,1],[0,1],[1,2],[2,3]]
- Output:
- 3
- Explanation:
Towns 0 and 1 have two separate roads, so they form a group; roads 1-2 and 2-3 are single links, leaving towns 2 and 3 alone: 3 groups.
Example 3
- Input:
- n = 5, edges = [[0,1],[1,2],[2,0],[2,3],[3,4],[4,2]]
- Output:
- 1
- Explanation:
Two triangles share town 2; closing any one road keeps everyone connected, so all five towns form a single group.
Constraints
1 ≤ n ≤ 5 * 104
0 ≤ edges.length ≤ 105
edges[i].length == 2
0 ≤ edges[i][j] < n
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)