Robust Component Count
Python
Hard
3 views
Problem Description
Read n m and then m edges. Some edge lines may be broken or have nodes out of range. Ignore invalid edges. Output number of connected components in resulting graph.
Input Format
First line n m. Next m lines edges u v.
Output Format
One integer components.
Sample Test Case
Input:
5 6
1 2
2 3
x y
3 6
4 5
2 3
Official Solution
import sys
from collections import deque
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
first=lines[0].split()
if len(first)<2:
sys.stdout.write('0')
raise SystemExit
n=int(first[0]); m=int(first[1])
g=[[] for _ in range(n+1)]
for i in range(1,1+m):
parts=(lines[i] if i<len(lines) else '').split()
if len(parts)<2:
continue
try:
u=int(parts[0]); v=int(parts[1])
except Exception:
continue
if u<1 or u>n or v<1 or v>n:
continue
g[u].append(v)
g[v].append(u)
vis=[False]*(n+1)
comp=0
for s in range(1,n+1):
if vis[s]:
continue
comp+=1
q=deque([s])
vis[s]=True
while q:
u=q.popleft()
for v in g[u]:
if not vis[v]:
vis[v]=True
q.append(v)
sys.stdout.write(str(comp))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!