그래프 예제

https://www.acmicpc.net/problem/2606

N = int(input())
M = int(input())

adj = [[] for _ in range(N)] # 인접 리스트 [ [], [], ... , []]

for _ in range(M):
    a, b = list(map(int, input().split()))
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
check = [0]*N
check[0] = 1

while True:
    
    new = False # if updated
    
    for i in range(N):
        if check[i] == 0:
            continue
        
        # check[i] == 1
        for j in adj[i]:
            if check[j] == 0:
                check[j] = 1 # update
                new = True
                
    if not new:
        break
            
count = 0
for i in range(1,N): # 1번 컴퓨터 제외
    if check[i] == 1:
        count += 1
        
print(count)

 

https://www.acmicpc.net/problem/5567

N = int(input())
M = int(input())

adj = [[] for _ in range(N)]

for _ in range(M):
    a, b = list(map(int, input().split()))
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
# 1.친구 배열 채우기
friend = [0]*N

for i in adj[0]:
    friend[i]=1
    
# 2.친구의 친구 배열 채우기
friend2 = [0]*N

for i in range(N):
    if friend[i]==0:
        continue
    
    # 친구인 경우
    for j in adj[i]:
        if j!=0 and friend[j]==0: # 친구가 아니고 친구의친구인 경우만
            friend2[j] = 1
            
print(sum(friend)+sum(friend2))