Graph InClass Problems
1. City Transport Network
## Adjacency matrix representation ##
n = int(input().strip())
m = int(input().strip())
adj_matrix = [[0]*n for _ in range(n)]
for _ in range(m):
u, v = map(int, input().split())
adj_matrix[u - 1][v - 1] = 1
for row in adj_matrix:
for ele in row:
print(ele,end=" ")
print()
2. City Transportation System
# Read number of cities (nodes)
n = int(input().strip())
# Read number of roads (edges)
m = int(input().strip())
adj_list = [[] for _ in range(n)]
# Read edges
for _ in range(m):
u, v = map(int, input().split())
# Since it is an undirected graph
adj_list[u - 1].append(v)
adj_list[v - 1].append(u)
for i in range(n):
print(f"City {i + 1}:", end=" ")
if i!=n-1:
adj_list[i].sort()
for neighbor in adj_list[i]:
print(neighbor, end=" ")
print()
3. Exploring City Routes
n = int(input().strip())
m = int(input().strip())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
for i in range(1, n + 1):
adj[i].sort()
start = int(input().strip())
visited = [False] * (n + 1)
stack = [start]
while stack:
node = [Link]()
if not visited[node]:
visited[node] = True
print(node, end=" ")
# So that smallest comes first when popped
for neighbor in reversed(adj[node]):
if not visited[neighbor]:
[Link](neighbor)
4. City Infrastructure Planning
from collections import deque
def bfs(adj, start, n):
visited = [False] * (n + 1)
queue = deque()
[Link](start)
visited[start] = True
while queue:
cur = [Link]()
print(cur, end=" ")
for neighbor in adj[cur]:
if not visited[neighbor]:
visited[neighbor] = True
[Link](neighbor)
n = int(input().strip())
m = int(input().strip())
adj = [[] for _ in range(n + 1)]
# Read edges
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
for i in range(1, n + 1):
adj[i].sort()
start = int(input().strip())
bfs(adj, start, n)
5. Road Network Connectivity
def dfs_iterative(adj, start, n):
visited = [False] * (n + 1)
stack = [start]
while stack:
node = [Link]()
if not visited[node]:
visited[node] = True
# Push neighbors in reverse order (optional for ordered traversal)
for neighbor in reversed(adj[node]):
if not visited[neighbor]:
[Link](neighbor)
return visited
# -------- Main Program --------
n = int(input().strip())
m = int(input().strip())
graph = [[] for _ in range(n + 1)]
reversed_graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
graph[u].append(v)
reversed_graph[v].append(u)
# Optional sorting (not mandatory for connectivity check)
for i in range(1, n + 1):
graph[i].sort()
reversed_graph[i].sort()
visited = dfs_iterative(graph, 1, n)
for i in range(1, n + 1):
if not visited[i]:
print("The road network is not connected.")
exit()
visited = dfs_iterative(reversed_graph, 1, n)
for i in range(1, n + 1):
if not visited[i]:
print("The road network is not connected.")
exit()
print("The road network is connected.")
6. Access to Libraries in HackerLand
from collections import deque
def bfs(graph, visited, src):
count = 1
visited[src] = True
queue = deque([src])
while queue:
cur = [Link]()
for neighbor in graph[cur]:
if not visited[neighbor]:
visited[neighbor] = True
count += 1
[Link](neighbor)
return count
# -------- Main Program --------
q = int(input().strip())
while q > 0:
n, m, c_lib, c_road = map(int, input().split())
# Create graph (1-based indexing)
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
# Read edges
for _ in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
total = 0
# If road cost >= library cost → build library in every city
if c_road >= c_lib:
total = n * c_lib
else:
# Find connected components
for i in range(1, n + 1):
if not visited[i]:
city_count = bfs(graph, visited, i)
total += c_lib + (city_count - 1) * c_road
print(total)
q -= 1
7. Shortest Route Finder in a City
from collections import deque
def bfs(graph, src, n):
visited = [False] * (n + 1)
dist = [-1] * (n + 1)
visited[src] = True
dist[src] = 0
queue = deque([src])
while queue:
cur = [Link]()
for neighbor in graph[cur]:
if not visited[neighbor]:
visited[neighbor] = True
dist[neighbor] = dist[cur] + 6
[Link](neighbor)
return dist
# -------- Main Program --------
q = int(input().strip())
while q > 0:
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
src = int(input().strip())
dist = bfs(graph, src, n)
# Print result excluding source node
for i in range(1, n + 1):
if i != src:
print(dist[i], end=" ")
print()
q -= 1
8. Edge Removal for Connected Components
from collections import deque
def bfs(start, graph, visited):
queue = deque([start])
visited[start] = True
while queue:
node = [Link]()
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = True
[Link](neighbor)
# -------- Main Program --------
n, m, k = map(int, input().split())
# Adjacency list (1-based indexing)
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
visited = [False] * (n + 1)
components = 0
# Count connected components using BFS
for i in range(1, n + 1):
if not visited[i]:
bfs(i, graph, visited)
components += 1
# If already more components than k → impossible
if components > k:
print(-1)
else:
max_removable_edges = m - (n - k)
print(max_removable_edges)
9. Finding a Mother Vertex in a Graph
from collections import deque
def bfs(start, graph, n):
visited = [False] * n
count = 0
queue = deque([start])
visited[start] = True
while queue:
node = [Link]()
count += 1
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = True
[Link](neighbor)
return count
# -------- Main Program --------
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
u, v = map(int, input().split())
graph[u].append(v)
mother_vertex = -1
# Try BFS from every vertex
for i in range(n):
reachable_count = bfs(i, graph, n)
if reachable_count == n:
mother_vertex = i
break
print(mother_vertex)
10. Identifying Cycles in Urban Road Networks
from collections import deque
def bfs(graph, visited, src):
queue = deque()
visited[src] = True
[Link]((src, -1)) # (node, parent)
while queue:
node, parent = [Link]()
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = True
[Link]((neighbor, node))
else:
# If visited and not parent → cycle
if neighbor != parent:
return True
return False
# -------- Main Program --------
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
cycle_found = False
# Important: Check all components
for i in range(n):
if not visited[i]:
if bfs(graph, visited, i):
cycle_found = True
break
if cycle_found:
print("Cycle Detected")
else:
print("No Cycle Detected")
11. Counting Islands
from collections import deque
def bfs(mat, i, j, rows, cols):
queue = deque()
[Link]((i, j))
mat[i][j] = 2 # mark as visited
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
x, y = [Link]()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and mat[nx][ny] == 1:
mat[nx][ny] = 2
[Link]((nx, ny))
# -------- Main Program --------
rows, cols = map(int, input().split())
mat = []
for _ in range(rows):
[Link](list(map(int, input().split())))
count = 0
for i in range(rows):
for j in range(cols):
if mat[i][j] == 1:
count += 1
bfs(mat, i, j, rows, cols)
print(count)