7066 : defaultdict 그래프
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
노드(정점)와 간선 정보가 주어질 때, 인접 리스트(Adjacency List) 형태의 무방향 그래프를 딕셔너리로 구축하고 쿼리를 처리하는 프로그램을 작성하십시오.
처리해야 하는 쿼리 형식은 다음과 같습니다.
-
-
[제약 조건]
• 노드 수 $N$: $1 \le N \le 1{,}000$, 간선 수 $E$: $1 \le E \le 5{,}000$
• 쿼리 수 $Q$: $1 \le Q \le 100$
처리해야 하는 쿼리 형식은 다음과 같습니다.
-
DEG v: 노드 v의 차수(Degree, 연결된 이웃 간선의 수)를 출력합니다.-
ADJ v: 노드 v의 이웃 노드들의 목록을 오름차순 정렬하여 공백으로 구분해 출력합니다. 이웃이 없다면 빈 줄을 출력합니다.[제약 조건]
• 노드 수 $N$: $1 \le N \le 1{,}000$, 간선 수 $E$: $1 \le E \le 5{,}000$
• 쿼리 수 $Q$: $1 \le Q \le 100$
입력 설명
첫째 줄에 전체 노드의 수 N과 간선의 수 E가 공백으로 구분되어 주어집니다. (1 ≤ N ≤ 1,000, 1 ≤ E ≤ 5,000)
둘째 줄부터 E개의 줄에 걸쳐 "A B" 형태로 무방향 간선으로 연결된 두 노드의 번호가 주어집니다. 노드 번호는 1부터 N까지의 정수입니다.
이후 다음 줄에 쿼리의 수 Q가 주어집니다. (1 ≤ Q ≤ 100)
그 다음 줄부터 Q개의 줄에 걸쳐 "DEG v" 또는 "ADJ v" 형태의 쿼리가 한 줄에 하나씩 주어집니다.
둘째 줄부터 E개의 줄에 걸쳐 "A B" 형태로 무방향 간선으로 연결된 두 노드의 번호가 주어집니다. 노드 번호는 1부터 N까지의 정수입니다.
이후 다음 줄에 쿼리의 수 Q가 주어집니다. (1 ≤ Q ≤ 100)
그 다음 줄부터 Q개의 줄에 걸쳐 "DEG v" 또는 "ADJ v" 형태의 쿼리가 한 줄에 하나씩 주어집니다.
출력 설명
Q개의 줄에 걸쳐 각 쿼리에 대한 수행 결과를 줄을 나누어 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 3
1 2
1 3
2 3
3
DEG 1
ADJ 3
DEG 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
1 2
0도움
파이썬의
무방향 그래프이므로 간선 "A B"에 대해
collections.defaultdict(list) 또는 defaultdict(set)를 그래프 저장용 딕셔너리로 이용하십시오.무방향 그래프이므로 간선 "A B"에 대해
graph[A].append(B)와 graph.append(A)를 둘 다 수행해야 합니다.