7061 : 공통 친구 찾기
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
인물들 간의 친구 관계가 주어질 때 임의의 두 사람이 공유하는 공통 친구의 수를 계산하는 프로그램을 작성하십시오.
친구 관계는 무방향(양방향)이며, 공통 친구란 두 사람 각각과 모두 친구인 제3자를 의미합니다.
[제약 조건]
• 친구 관계 수 $N$: $1 \le N \le 1{,}000$
• 쿼리 수 $Q$: $1 \le Q \le 100$
친구 관계는 무방향(양방향)이며, 공통 친구란 두 사람 각각과 모두 친구인 제3자를 의미합니다.
[제약 조건]
• 친구 관계 수 $N$: $1 \le N \le 1{,}000$
• 쿼리 수 $Q$: $1 \le Q \le 100$
입력 설명
첫째 줄에 전체 친구 관계의 수 N이 주어집니다. (1 ≤ N ≤ 1,000)
둘째 줄부터 N개의 줄에 걸쳐 각 줄에 "A B" 형식으로 친구 관계인 두 사람의 이름이 공백으로 구분되어 주어집니다. 이름은 소문자 단어입니다.
그 다음 줄에 공통 친구 수를 물어보는 쿼리의 개수 Q가 주어집니다. (1 ≤ Q ≤ 100)
이후 Q개의 줄에 걸쳐 공통 친구 수를 계산할 대상자 "X Y"가 공백으로 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 각 줄에 "A B" 형식으로 친구 관계인 두 사람의 이름이 공백으로 구분되어 주어집니다. 이름은 소문자 단어입니다.
그 다음 줄에 공통 친구 수를 물어보는 쿼리의 개수 Q가 주어집니다. (1 ≤ Q ≤ 100)
이후 Q개의 줄에 걸쳐 공통 친구 수를 계산할 대상자 "X Y"가 공백으로 구분되어 주어집니다.
출력 설명
Q개의 줄에 걸쳐 각 쿼리에 대한 두 사람의 공통 친구 수를 정수로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
alice bob
alice charlie
david bob
david charlie
2
alice david
bob charlie
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
2도움
각 사람별 친구 목록을 딕셔너리의 집합 자료형으로 보관하십시오.
그 후 X와 Y의 공통 친구는 두 사람의 친구 집합의 교집합(
friends = {'alice': {'bob', 'charlie'}, ...}그 후 X와 Y의 공통 친구는 두 사람의 친구 집합의 교집합(
friends[X] & friends[Y])을 구해 그 크기를 반환하면 쉽게 해결됩니다.