跳转至

Friend Circle Queries

1、题目描述

The population of HackerWorld is 10^{9} . Initially, none of the people are friends with each other. In order to start a friendship, two persons a and b have to shake hands, where 1<=a,b,<=10^{9}. The friendship relation is transitive, that is if a and b shake hands with each other, a and friends of a become friends with b and friends of b.

You will be given q queries. After each query, you need to report the size of the largest friend circle (the largest group of friends) formed after considering that query.

For example, your list of queries is:

1 2
3 4
2 3

First, 1 and 2 shake hands, forming a circle of 2 . Next, 3and 4 do the same. Now there are two groups of 2 friends. When 2 and 3 become friends in the next query, both groups of friends are added together to make a circle of 4 friends. We would print

2
2
4

Function Description

Complete the function maxCircle in the editor below. It must return an array of integers representing the size of the maximum circle of friends after each query.

maxCircle has the following parameter(s):

  • queries: an array of integer arrays, each with two elements indicating a new friendship

Input Format

The first line contains an integer q, , the number of queries to process. Each of the next q lines consists of two space-separated integers denoting the 2-D array queries.

Constraints

  • 1<=q<=10^{5}
  • 1<=queries[i][0],queries[i][1]\le10^{9}\ for\ 0 \le i<q
  • queries[i][0] \ne queries[i][1]

Output Format

Return an integer array of size q , whose value at index is the size of largest group present after processing i^{th}the query.

Sample Input 0

2
1 2
1 3

Sample Output 0

2
3

Explanation 0

In the first query, 1and2 shake hands. So, the size of largest group of friends is 2 (as no other friendships exist). After the second query, 1,2 and 3 all become friends, as 1 shakes hand with 3 , 2 also become friends with 3 as he was already a friend of 1 .

Sample Input 1

4
1000000000 23
11 3778
7 47
11 1000000000

Sample Output 1

2
2
2
4

Explanation 1

After first query, person 1000000000 and person 23 become friends. So, the largest group size is 2 . After the second query, person 11 and person 3778 become friends. So, the largest group size is still 2. After the third query, person 7 and 47 person become friends. Answer is still 2. After the last query, person 11 and person 1000000000 become friends, which means23 ,11 ,1000000000 and 3778 all become friends. Hence, the answer now increased to 4.

Sample Input 2

6
1 2
3 4
1 3
5 7
5 6
7 4

Sample Output 2

2
2
4
4
4
7

Explanation 2

Friend circles after each iteration:

1   [1,2]
2   [1,2],[3,4]
3   [1,2,3,4]
4   [1,2,3,4],[5,7]
5   [1,2,3,4],[5,7,6]
6   [1,2,3,4,5,6,7]

2、解题思路

  • 使用带计数的并查集
  • 将每个人看成一个节点,关系看成边,每一步看最大的连通图中的数量加入结果集
#!/bin/python3

import math
import os
import random
import re
import sys
import itertools


class DFU:
    def __init__(self, length):
        self.data = list(range(length))
        self.size = [1] * length

    def find(self, x):
        if self.data[x] != x:
            self.data[x] = self.find(self.data[x])
        return self.data[x]

    def union(self, x, y):
        xp = self.find(x)
        yp = self.find(y)
        if xp != yp:
            if self.size[xp] > self.size[yp]:
                self.size[xp] += self.size[yp]
                self.data[yp] = xp
            else:
                self.size[yp] += self.size[xp]
                self.data[xp] = yp

    def get_size(self, x):
        return self.size[x]

    def count(self):
        res = 0
        for index, i in enumerate(self.data):
            if index == i:
                res += 1
        return res


# Complete the maxCircle function below.
def maxCircle(queries):
    res = []
    max_friends = 2
    mapping = {}
    print(queries)
    for index, x in enumerate(set(itertools.chain(*queries))):
        mapping[x] = index

    d = DFU(len(mapping))

    for x, y in queries:
        d.union(mapping[x], mapping[y])
        max_friends = max(max_friends, d.size[d.find(mapping[x])])
        res.append(max_friends)

    return res


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input())

    queries = []

    for _ in range(q):
        queries.append(list(map(int, input().rstrip().split())))

    ans = maxCircle(queries)

    fptr.write('\n'.join(map(str, ans)))
    fptr.write('\n')

    fptr.close()