fork(1) download
copy 
  1. # your code goes here
  2. def articulation_points_and_bridges(n, roads):
  3.     def dfs(u, parent):
  4.         nonlocal time, articulation_points, bridges
  5.         visited[u] = True
  6.         discovery[u] = low[u] = time
  7.         time += 1
  8.         children = 0
  9.         for v in graph[u]:
  10.             if not visited[v]:
  11.                 children += 1
  12.                 parent[v] = u
  13.                 dfs(v, parent)
  14.                 low[u] = min(low[u], low[v])
  15.                 if low[v] > discovery[u]:
  16.                     bridges.append((u, v))
  17.                 if parent[u] == -1 and children > 1:
  18.                     articulation_points.add(u)
  19.                 if parent[u] != -1 and low[v] >= discovery[u]:
  20.                     articulation_points.add(u)
  21.             elif v != parent[u]:
  22.                 low[u] = min(low[u], discovery[v])
  23.  
  24.     graph = [[] for _ in range(n + 1)]
  25.     for road in roads:
  26.         u, v = road
  27.         graph[u].append(v)
  28.         graph[v].append(u)
  29.  
  30.     visited = [False] * (n + 1)
  31.     discovery = [float('inf')] * (n + 1)
  32.     low = [float('inf')] * (n + 1)
  33.     parent = [-1] * (n + 1)
  34.     time = 0
  35.     articulation_points = set()
  36.     bridges = []
  37.  
  38.     for i in range(1, n + 1):
  39.         if not visited[i]:
  40.             dfs(i, parent)
  41.  
  42.     return articulation_points, bridges
  43.  
  44. # Hidden Test Cases
  45. hidden_test_cases = [
  46.     # Easy Cases
  47.     (1, []),  # Single intersection with no roads
  48.     (5, [[1, 2], [2, 3], [3, 4], [4, 5]]),  # Linear road network with no articulation points or bridges
  49.     (4, [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]),  # Complete graph with multiple articulation points and bridges
  50.  
  51.     # Medium Cases
  52.     (4, [[1, 2], [2, 3], [3, 4], [1, 3]]),  # Grid-like road network with multiple articulation points but no bridges
  53.     (5, [[1, 2], [1, 3], [2, 3], [3, 4], [4, 5], [2, 5]]),  # Random road network with varying degrees of connectivity
  54.     (5, [[1, 2], [2, 3], [3, 4], [4, 5], [5, 1], [2, 4], [3, 5]]),  # Road network with loops and cycles
  55.     (4, [[1, 2], [1, 2], [2, 3], [2, 3], [3, 4], [4, 4]]),  # Road network with duplicate edges and self-loops
  56.  
  57.     # Hard Cases
  58.     (8, [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 2], [8, 3]]),  # Large-scale road network with thousands of intersections and roads
  59.     (7, [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 5], [4, 6], [5, 6], [5, 7]]), # Highly interconnected road network with numerous articulation points and bridges
  60.     (8, [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [4, 8], [3, 7]])   # Road network with complex topology, including multiple disconnected components
  61. ]
  62.  
  63. # Function Calls for Hidden Test Cases
  64. for i, (n, roads) in enumerate(hidden_test_cases, 1):
  65.     print(f"Hidden Test Case {i}:")
  66.     print("Input:", n)
  67.     for road in roads:
  68.         print(*road)
  69.     articulation_points, bridges = articulation_points_and_bridges(n, roads)
  70.     print("Output:")
  71.     print("Articulation Points:", ", ".join(map(str, articulation_points)))
  72.     print("Bridges:", ", ".join(map(str, bridges)))
  73.     print()
  74.  
Success #stdin #stdout 0.04s 9604KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Hidden Test Case 1:
Input: 1
Output:
Articulation Points: 
Bridges: 

Hidden Test Case 2:
Input: 5
1 2
2 3
3 4
4 5
Output:
Articulation Points: 2, 3, 4
Bridges: (4, 5), (3, 4), (2, 3), (1, 2)

Hidden Test Case 3:
Input: 4
1 2
1 3
1 4
2 3
2 4
3 4
Output:
Articulation Points: 
Bridges: 

Hidden Test Case 4:
Input: 4
1 2
2 3
3 4
1 3
Output:
Articulation Points: 3
Bridges: (3, 4)

Hidden Test Case 5:
Input: 5
1 2
1 3
2 3
3 4
4 5
2 5
Output:
Articulation Points: 
Bridges: 

Hidden Test Case 6:
Input: 5
1 2
2 3
3 4
4 5
5 1
2 4
3 5
Output:
Articulation Points: 
Bridges: 

Hidden Test Case 7:
Input: 4
1 2
1 2
2 3
2 3
3 4
4 4
Output:
Articulation Points: 2, 3
Bridges: (3, 4), (2, 3), (1, 2)

Hidden Test Case 8:
Input: 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 2
8 3
Output:
Articulation Points: 2
Bridges: (1, 2)

Hidden Test Case 9:
Input: 7
1 2
1 3
2 3
2 4
3 4
3 5
4 5
4 6
5 6
5 7
Output:
Articulation Points: 5
Bridges: (5, 7)

Hidden Test Case 10:
Input: 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 8
3 7
Output:
Articulation Points: 2, 3
Bridges: (2, 3), (1, 2)
https://ideone.com/MS07Lv
language:
Python 3 (python  3.9.5)
created:
18 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!