Problem 10608 Friends, Largest Friend Group

Apr 26, 201214

AI Translation

This post is translated from Chinese into English through AI.View Original

AI-generated summary

In a town with N citizens, the problem involves determining the largest group of friends based on the principle that a friend's friend is also considered a friend. Given N and M, where M pairs of integers represent friendships between citizens, the task is to calculate the size of the largest friend group. The approach involves assigning group numbers to friends, merging groups when necessary, and updating the total count of distinct friend groups accordingly. The process starts with initializing an array for group numbers and counts.

In the town, there are N people. According to a saying: "The friends of my friends are also my friends." If A and B are friends, and B and C are friends, then C and A are also friends.

Read in two integers N and M, where N represents the citizens numbered from 1 to N in the town, and the following M lines contain two integers a and b, indicating that citizen a and citizen b are friends. Finally, please calculate the number of the largest friend group in this town.

In fact, you only need to define a friend group number for the friend groups. If neither party has a friend group number, assign both a new friend group number and increase the count of friend group numbers to 2; if one of them does not have a friend group number, add them to the numbered friend group; if both have friend group numbers, change all friends of one party to the other party's number and add the count of the other party's friends to the total.

Initially, declare an array and initialize the friend group numbers and the count of friend groups: