Союз-находка выражается как социальная сеть

Ответ 1

Когда вы добавляете дружбу в структуру данных поиска union, вы можете заметить, что это приводит к объединению двух компонентов графа. Просто продолжайте добавлять края до тех пор, пока не произойдет N-1 этих слияний.

В псевдокодовой форме:

G := UnionFind(1..N)
count := 0
for timestamp, p1, p2 in friendships {
    if G.Find(p1) != G.Find(p2) {
        G.Union(p1, p2)
        count++
        if count == N-1 {
            return timestamp
        }
    }
}
return +infinity

Ответ 2

Хорошо, чтобы решить это упражнение, я сделал предположение, что файл журнала будет выглядеть примерно так:

0 1 2015-08-14 18:00:00
1 9 2015-08-14 18:01:00
0 2 2015-08-14 18:02:00
0 3 2015-08-14 18:04:00
0 4 2015-08-14 18:06:00
0 5 2015-08-14 18:08:00
0 6 2015-08-14 18:10:00
0 7 2015-08-14 18:12:00
0 8 2015-08-14 18:14:00
1 2 2015-08-14 18:16:00
1 3 2015-08-14 18:18:00
1 4 2015-08-14 18:20:00
1 5 2015-08-14 18:22:00
2 1 2015-08-14 18:24:00
2 3 2015-08-14 18:26:00
2 4 2015-08-14 18:28:00
5 5 2015-08-14 18:30:00

Если 2 первых числа являются членами, которые создали дружбу, следуйте по метке времени.

Еще одна важная вещь, которую нужно вызывать, заключается в том, что в упражнении упоминается, что файл отсортирован, поэтому я решил сортировать его по возрастанию.

С помощью этой информации вы можете использовать структуру данных WeightedQuickUnionFind, предоставленную в классе, и простой процесс: файл, выполняющий операцию объединения с членами, после того, как вы сделаете объединение вы можете спросить, сколько компонентов находится в структуре, если есть только одно, что означает, что все члены имеют эквивалентное отношение.

Вот код, который я сделал:

public static void main(String[] args) {

        int n = StdIn.readInt();
        WeightedQuickUnion uf = new WeightedQuickUnion(n);
        String date, time;
        //timestamps are sorted ascending
        while (!StdIn.isEmpty()) {

            int p = StdIn.readInt();
            int q = StdIn.readInt();
            date = StdIn.readString();
            time = StdIn.readString();


            uf.union(p, q);

            StdOut.println("["+p+","+q+"]");

            if(uf.getComponents() == 1){
                StdOut.println("All members were connected at: " + date + time);
                break;
            }

        }

Производительность будет M lg N, потому что вы выполняете итерацию М раз (количество строк в файле журнала) и операции объединения: lg n.

Ответ 3

Социальная сеть может быть представлена в виде дерева или графика, где каждый узел имеет от 0 до n соединений.

Основная часть необходимой вам структуры данных - это массив целых чисел, где каждый индекс элемента можно интерпретировать как идентификатор члена социальной сети, а значение - это идентификатор другого члена, который является корневым для первого.

Вам нужно прочитать журнал и выполнить операцию union в вашей структуре данных для каждой записи журнала (построение дерева) и проанализировать два критерия

• у каждого участника есть связь (Set<Integer> haveConnection)
• есть только один корень global (потому что с самого начала у вас будет много не связанных подсетей с собственными корнями) (Set<Integer> roots)

Как только оба критерия удовлетворены - все участники вашей сети подключены.

Удачи!

Ответ 4

Чтобы выяснить, все ли участники подключены, я использовал концепцию взвешенного быстрого объединения. Если размер дерева становится равным n, то мы можем сказать, что все члены связаны. Мой код:

class MyClas {
    private int[] a;
    private int[] size;
    int N=0;
    public MyClas(int n){
        N=n;
        a = new int[n];
        size = new int[n];
        for(int i=0;i<n;i++){
            a[i]=i;
            size[i]=1;
        }
    }
    private int root(int x){
        while(x != a[x]){
            x=a[x];
        }
        return x;
    }
    public boolean connected(int p, int q){
        return root(p)==root(q);
    }
    public void union(int p,int q, String timestamp){
        int i = root(p);
        int j = root(q);
        if(i == j) return;
        if(size[i] < size[j]){
            a[i] = j;
            size[j]+=size[i];
            if(size[j]==N){
                System.out.println("All Members are connected at Timestamp"+ timestamp);
            }
        }
        else{
            a[j] = i;
            size[i]+=size[j];
            if(size[i]==N){
                System.out.println("All Members are connected at Timestamp"+ timestamp);
            }
        }
    }

}
public class MyClass {
    public static void main(String args[]) {
      MyClas obj = new MyClas(6);
      obj.union(1,5, "2019-08-14 18:00:00");
      obj.union(2,4, "2019-08-14 18:00:01");
      obj.union(1,3, "2019-08-14 18:00:02");
      obj.union(5,2, "2019-08-14 18:00:03");
      obj.union(0,3,"2019-08-14 18:00:04");
      obj.union(2,1,"2019-08-14 18:00:05");

    }
}

Ответ 5

Ответ, предоставленный Андресом, является правильным. Есть и другой способ. Вы можете использовать дополнительное пространство, пропорциональное N элементам здесь. Таким образом, вы можете сохранить массив общего количества узлов в дереве и в функции объединения после слияния обоих деревьев, которые вам нужно будет добавить количество узлов в объединенном дереве с количеством узлов в дереве, которое является корнем обоих. Поэтому после добавления вам просто нужно проверить, равно ли общее число узлов в новом дереве N. Если это так, это будет самое раннее время, когда все члены N дружат друг с другом.

Ответ 6

Добавление в @Andrés Ответ. Вот метод для проверки того, что все они подключены или нет, для добавления в класс WeightedQuickUnionFind.

public boolean isAllConnected(){
    int N = id.length;
    while(--N>0 && id[N] == id[0]);
    return N == 0;
}