Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
Please use python and python file i/o to solve the problem. Create an input file input3_1.txt as shown below, solve the problem and print the output to output3_1.txt file as shown in the question. Sample Input Explanation: In sample input 2, Query 0: Initially, there are 8 people in the village who do not know each other. {1} {2} {3} {4} {5} {6} {7} {8} Query 1: After person 2 and person 4 becoming friends: {1} {2,4} {3} {5} {6} {7} {8} The output is 2, since the size of the friends circle {2,4} is 2. Query 2: After person 4 and person 5 becoming friends: {1} {2,4,5} {3} {6} {7} {8} The output is 3, since the size of the friends circle {2,4,5} is 3. Query 3: After person 3 and person 6 becoming friends: {1} {2,4,5} {3,6} {7} {8} The output is 2, since the size of the friends circle {3,6} is 2. Query 4: After person 4 and person 7 becoming friends: {1} {2,4,5,7} {3,6} {8} The output is 4, since the size of the friends circle {2,4,5,7} is 4. Query 5: After person 3 and person 1 becoming friends: {2,4,5,7} {1,3,6} {8} The output is 3, since the size of the friends circle {1,3,6} is 3. Query 6: Since the person 2 and person 7 are already in the same friend circle, nothing changes: {2,4,5,7} {1,3,6} {8} The output is 4, since the size of the friends circle {2,4,5,7} is 4. Query 7: After person 6 and person 2 becoming friends: {1,2,3,4,5,6} {7} {8} The output is 7, since the size of the friends circle {1,2,3,4,5,6} is 7.

Please use python and python file i/o to solve the problem. Create an input file input3_1.txt as shown below, solve the problem and print the output to output3_1.txt file as shown in the question. Sample Input Explanation: In sample input 2, Query 0: Initially, there are 8 people in the village who do not know each other. {1} {2} {3} {4} {5} {6} {7} {8} Query 1: After person 2 and person 4 becoming friends: {1} {2,4} {3} {5} {6} {7} {8} The output is 2, since the size of the friends circle {2,4} is 2. Query 2: After person 4 and person 5 becoming friends: {1} {2,4,5} {3} {6} {7} {8} The output is 3, since the size of the friends circle {2,4,5} is 3. Query 3: After person 3 and person 6 becoming friends: {1} {2,4,5} {3,6} {7} {8} The output is 2, since the size of the friends circle {3,6} is 2. Query 4: After person 4 and person 7 becoming friends: {1} {2,4,5,7} {3,6} {8} The output is 4, since the size of the friends circle {2,4,5,7} is 4. Query 5: After person 3 and person 1 becoming friends: {2,4,5,7} {1,3,6} {8} The output is 3, since the size of the friends circle {1,3,6} is 3. Query 6: Since the person 2 and person 7 are already in the same friend circle, nothing changes: {2,4,5,7} {1,3,6} {8} The output is 4, since the size of the friends circle {2,4,5,7} is 4. Query 7: After person 6 and person 2 becoming friends: {1,2,3,4,5,6} {7} {8} The output is 7, since the size of the friends circle {1,2,3,4,5,6} is 7.

icon
Related questions
Question

Please use python and python file i/o to solve the problem. Create an input file input3_1.txt as shown below, solve the problem and print the output to output3_1.txt file as shown in the question.

Sample Input Explanation:
In sample input 2,
Query 0: Initially, there are 8 people in the village who do not
know each other.
{1} {2} {3} {4} {5} {6} {7} {8}
Query 1: After person 2 and person 4 becoming friends:
{1} {2,4} {3} {5} {6} {7} {8}

The output is 2, since the size of the friends circle {2,4} is
2.
Query 2: After person 4 and person 5 becoming friends:
{1} {2,4,5} {3} {6} {7} {8}
The output is 3, since the size of the friends circle {2,4,5} is
3.
Query 3: After person 3 and person 6 becoming friends:
{1} {2,4,5} {3,6} {7} {8}
The output is 2, since the size of the friends circle {3,6} is
2.
Query 4: After person 4 and person 7 becoming friends:
{1} {2,4,5,7} {3,6} {8}
The output is 4, since the size of the friends circle {2,4,5,7}
is 4.
Query 5: After person 3 and person 1 becoming friends:
{2,4,5,7} {1,3,6} {8}
The output is 3, since the size of the friends circle {1,3,6} is
3.
Query 6: Since the person 2 and person 7 are already in the same
friend circle, nothing changes:
{2,4,5,7} {1,3,6} {8}
The output is 4, since the size of the friends circle {2,4,5,7}
is 4.
Query 7: After person 6 and person 2 becoming friends:

{1,2,3,4,5,6} {7} {8}
The output is 7, since the size of the friends circle
{1,2,3,4,5,6} is 7.

Study material: http://www.shafaetsplanet.com/?p=763 There is a group of N people living in a small village. They live in their own house. Although they are all neighbors, they don't all know each other very well. Each person in that village has their own unique identity labeled with an integer value between 1 to N. Initially, the villagers don't have any friends. As time passes by, they begin to make friendship between themselves. In this problem, you will be given a description of K friendships. You have to print an integer value which denotes the size of their friend circle. Suppose, there are five people living in the village labeled with 1,2,3,4 and 5. Initially, the size of each friend circle is one, since no friendship has been created yet. One day, person 1 and person 2 become friends. So the size of their friend circle becomes two. Next day, person 3 and person 4 become friends and the size of their friendship becomes two as well. After a few days, person 1 and person 4 become friends. Now the size of their friend circle becomes four consisting of persons 1,2,3 and 4. Input Format: The input consists of two integers, separated by a space, denoting the number of people in the village, N (1 ≤ N≤ 10^5) and the number of queries that will follow, K (1 ≤ K ≤ 10^5). The next K lines contain two integers A and B, each (1 ≤ A₁, B₁ S N and A₁ != B₁), separated by a space, representing two people who have become friends as a result of the query.
Transcribed Image Text:Study material: http://www.shafaetsplanet.com/?p=763 There is a group of N people living in a small village. They live in their own house. Although they are all neighbors, they don't all know each other very well. Each person in that village has their own unique identity labeled with an integer value between 1 to N. Initially, the villagers don't have any friends. As time passes by, they begin to make friendship between themselves. In this problem, you will be given a description of K friendships. You have to print an integer value which denotes the size of their friend circle. Suppose, there are five people living in the village labeled with 1,2,3,4 and 5. Initially, the size of each friend circle is one, since no friendship has been created yet. One day, person 1 and person 2 become friends. So the size of their friend circle becomes two. Next day, person 3 and person 4 become friends and the size of their friendship becomes two as well. After a few days, person 1 and person 4 become friends. Now the size of their friend circle becomes four consisting of persons 1,2,3 and 4. Input Format: The input consists of two integers, separated by a space, denoting the number of people in the village, N (1 ≤ N≤ 10^5) and the number of queries that will follow, K (1 ≤ K ≤ 10^5). The next K lines contain two integers A and B, each (1 ≤ A₁, B₁ S N and A₁ != B₁), separated by a space, representing two people who have become friends as a result of the query.
Output Format: For each query, output a single integer on a new line representing the size of the friend circle that the two people belong to after becoming friends. Sample Input/Output: Sample Input 1 53 1 2 34 14 Sample Input 2 8 7 24 45 36 47 3 1 27 62 Sample Output 1 2 ANN 2 4 Sample Output 2 NM NMAN 2 3 2 7
Transcribed Image Text:Output Format: For each query, output a single integer on a new line representing the size of the friend circle that the two people belong to after becoming friends. Sample Input/Output: Sample Input 1 53 1 2 34 14 Sample Input 2 8 7 24 45 36 47 3 1 27 62 Sample Output 1 2 ANN 2 4 Sample Output 2 NM NMAN 2 3 2 7
Expert Solution
steps

Step by step

Solved in 3 steps with 1 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer