首页 > 试题广场 >

朋友圈(后端开发卷)

[编程题]朋友圈(后端开发卷)
  • 热度指数:8068 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
现在有 105 个用户,编号为 1- 105,现在已知有 m 对关系,每一对关系给你两个数 x 和 y ,代表编号为 x 的用户和编号为 y 的用户是在一个圈子中,例如: A 和 B 在一个圈子中, B 和 C 在一个圈子中,那么 A , B , C 就在一个圈子中。现在想知道最多的一个圈子内有多少个用户。

数据范围:
进阶:空间复杂度 ,时间复杂度

输入描述:
第一行输入一个整数T,接下来有T组测试数据。
对于每一组测试数据:第一行输入1个整数n,代表有n对关系。
接下来n行,每一行输入两个数x和y,代表编号为x和编号为y的用户在同一个圈子里。
1 ≤ T ≤ 10
1 ≤ n ≤ 2*106
1 ≤ x, y ≤ 105


输出描述:
对于每组数据,输出一个答案代表一个圈子内的最多人数
示例1

输入

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

输出

4
2
给一个chatgpt的答案:

可以使用并查集(Union-Find)来解决此问题。首先将所有用户看作一个单独的圈子,然后遍历所有关系对,将它们所在的圈子合并起来。最终,统计每个圈子的大小并找到最大值即可。

以下是Python代码的示例实现:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.size[root_x] < self.size[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]

def max_circle(m):
    uf = UnionFind(105)
    for x, y in m:
        uf.union(x-1, y-1)
    return max(uf.size)

# Example usage:
m = [(1, 2), (2, 3), (4, 5), (6, 7), (7, 8), (9, 10), (100, 101)]
max_size = max_circle(m)
print(max_size) # Output: 4

其中,UnionFind类实现了并查集,其中parent数组用于记录每个节点的父节点,size数组用于记录每个圈子的大小。find方法实现了路径压缩,使查找操作的时间复杂度接近常数。union方法实现了按秩合并和路径压缩,使合并操作的时间复杂度接近常数。

max_circle函数使用UnionFind类来处理关系对,然后找到最大圈子的大小并返回。

================================
感谢chatgpt,可以取代我了

发表于 2023-03-26 16:58:25 回复(0)
import sys
class unionfind():
    def __init__(self, n):
        self.father = list(range(n+1))
        self.size = [1] * (n+1)
    def find(self, x):
        if self.father[x] == x:
            return x
        self.father[x] = self.find(self.father[x])
        return self.father[x]
    def merge(self,x,y):
        fx = self.find(x)
        fy = self.find(y)
        if fx != fy:
            self.father[fy] = fx
            self.size[fx] += self.size[fy]
        return

n1 = int(input())
for i in range(n1):
    n2 = int(input())
    un = unionfind(1000000)
    res = 1
    for j in range(n2):
        line = sys.stdin.readline().strip()
        a,b = list(map(int, line.split()))
        un.merge(a,b)
        res = max(res,un.size[un.find(a)])
    print(res)
发表于 2021-08-24 23:38:31 回复(0)