04109: 公共朋友-Common Friends

http://cs101.openjudge.cn/practice/04109/

小明和小红去参加party。会场中总共有n个人，这些人中有的是朋友关系，有的则相互不认识。朋友关系是相互的，即如果A是B的朋友，那么B也是A的朋友。小明和小红想知道其中某两个人有多少个公共的朋友。

输入

第一行为一个正整数c，代表测试数据的个数。接下来是c组测试数据。

对于每组测试数据，第一行是三个数字n(2<=n<=100)，m和k，分别表示会场中的人数，已知的朋友关系数目，问题的数目。接下来的m行，每行用两个数字i和j(1<=i,j<=n)表示了一个朋友关系，表示第i个人和第j个人是朋友关系。接下来的k行，每行用两个数字i和j(1<=i,j<=n)表示一个问题，请问第i个人和第j个人有多少公共的朋友。

输出

对于第i组测试数据，首先输出一行”Case i:”，接下来得k行代表了k个问题，每行输出第i个人和第j个人有多少公共的朋友。

样例输入

样例输出

Case 1:
1
0
Case 2:
2
1

python

def count_common_friends(n, m, k, friend_connections, queries):
    # Create a dictionary to store friend connections
    friends_dict = {}
    for i in range(1, n + 1):
        friends_dict[i] = set()

    # Update the dictionary with friend connections
    for i, j in friend_connections:
        friends_dict[i].add(j)
        friends_dict[j].add(i)

    # Count common friends for each query
    results = []
    for i, j in queries:
        common_friends = len(friends_dict[i].intersection(friends_dict[j]))
        results.append(common_friends)

    return results


def main():
    test_cases = int(input())
    for case in range(1, test_cases + 1):
        n, m, k = map(int, input().split())
        friend_connections = []
        queries = []

        # Read friend connections
        for _ in range(m):
            i, j = map(int, input().split())
            friend_connections.append((i, j))

        # Read queries
        for _ in range(k):
            i, j = map(int, input().split())
            queries.append((i, j))

        # Count common friends and output the results
        print(f"Case {case}:")
        results = count_common_friends(n, m, k, friend_connections, queries)
        for result in results:
            print(result)


if __name__ == "__main__":
    main()

04109: 公共朋友-Common Friends ​

04109: 公共朋友-Common Friends