查找网络中的最大用户数

Question

我有m行，值x和y用空格分隔，表示用户id。这就像用户x在Facebook或Instagram上关注用户y一样。现在，如果我们有一对z和y，那么既然z关注y，因为我们已经有了一个组[x，y]，那么我们可以合并z形成[x，y，z]

示例：

1 2
3 4
5 6
1 5

我们可以有以下小组：

[1 2 5 6]和[3 4]，最大组[1，2，5，6]的长度为4将是答案。

这是我的方法：

public int process(int m, int[][] arr) {
List<Set<Integer>> list = new ArrayList<>();

int ans = 0;
for(int i=0; i<m; i++) {
int x = arr[i][0], y = arr[i][1];
if(j ==0) {
Set<Integer> set = new HashSet<>();
list.add(set);
set.add(x);
set.add(y);
ans = 2;
continue;
}
boolean found = false;
for(Set<Integer> set : list) {
if(set.contains(x) || set.contains(y)) {
set.add(x);
set.add(y);
ans = Math.max(ans, set.size());
found = true;
break;
}
}
if(!found) {
Set<Integer> set = new HashSet<>();
list.add(set);
set.add(x);
set.add(y);
}
}
return ans;
} 

我的方法本身是错误的，因为我生成的列表没有正确地对元素进行分组。如何解决这个问题。此外，输入数组长度可以高达100000，因此需要在较低的时间复杂性中解决此问题。

限制：

x and y can range from 1 to 10^5
aray length can be up to 10^6

Answer 1

您可以使用不相交集，从每个大小为1的组开始，并在合并时合并大小。

public int process(int m, int[][] arr) {
class DS {
static int[] p = new int[100001];
static int[] size = new int[100001];
static int find(int x) {
return x == p[x] ? x : (p[x] = find(p[x]));
}
static int merge(int x, int y) {
int rx = find(x), ry = find(y);
if (rx != ry) {
p[rx] = ry;
size[ry] += size[rx];
}
return size[ry];
}
static void init() {
for (int i = 0; i < p.length; i++) {
p[i] = i;
size[i] = 1;
}
}
}
DS.init();
int ans = 0;
for (int[] pair: arr) 
ans = Math.max(ans, DS.merge(pair[0], pair[1]));
return ans;
}

Answer 2

此数据可以表示为Disjointed Graph。问题归结为在这个图中找到最大的连通分量。

为此，我们需要对Graph的顶点(表示用户(进行迭代。对于每个尚未检查的顶点，我们需要启动遍历逻辑来找到该顶点所属的组的大小(为此，下面的代码中使用了DFS算法实现(。

这种方法的时间复杂度将是线性的O(n((假设存在nids(，因为每个顶点将只被检查一次。

class UserGraph {

private Map<Integer, User> userById = new HashMap<>(); // contains all vertices of the graph

private UserGraph() {} // no way and no need to invoke this constructor from the outside of the class

public static UserGraph getInstance(int[][] arr) {
UserGraph graph = new UserGraph();
for (int[] connection: arr) {
graph.addConnection(connection[0], connection[1]);
}
return graph;
}

public void addConnection(int id1, int id2) { // for simplicity connection would be mutual
User user1 = userById.computeIfAbsent(id1, User::new);
User user2 = userById.computeIfAbsent(id2, User::new);
user1.addFollower(user2);
user2.addFollower(user1);
}

public int getLargestGroupSize() {
Set<User> seen = new HashSet<>();
int maxSize = 0;
for (User user: userById.values()) {
if (seen.add(user)) {
int groupSize = getGroupSize(seen, user);
maxSize = Math.max(maxSize, groupSize);
}
}
return maxSize;
}

public int getGroupSize(Set<User> seen, User user) {
Deque<User> stack = new ArrayDeque<>();
stack.add(user);
int groupSize = 0;
while (!stack.isEmpty()) {
User current = stack.pop();
groupSize++;

for (User follower: current.getFollowers()) {
if (seen.add(follower)) stack.push(follower);
}
}
return groupSize;
}

private static class User {
private int id;
private List<User> followers = new ArrayList<>();

public User(int id) {
this.id = id;
}

public void addFollower(User user) {
followers.add(user);
}

public List<User> getFollowers() {
return followers;
}
}
}

main()

public static void main(String[] args) {
int[][] arr = {
{1, 2},
{3, 4},
{5, 6},
{1, 5}
};

UserGraph graph = UserGraph.getInstance(arr);
System.out.println(graph.getLargestGroupSize());
}

输出：

4