Самый ранний момент, когда все подружились в C# и Typescript

Самый ранний момент, когда все подружились в C# и Typescript

Ссылка на проблему LeetCode:

Интуиция

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

Подход

Алгоритм, который мы здесь используем, называется алгоритмом Union-Find. Алгоритм Union-Find, также известный как структура данных Disjoint-Set, представляет собой структуру данных и алгоритм, используемые для эффективного отслеживания и объединения непересекающихся наборов. Он предоставляет операции для создания наборов, определения того, к какому набору принадлежит элемент, и объединения наборов вместе.

Алгоритм Union-Find обычно используется в алгоритмах графов, таких как алгоритм Крускала для поиска минимального остовного дерева или обнаружения циклов в графе. Он поддерживает набор непересекающихся множеств и обеспечивает две основные операции:

1. Объединение: объединение двух наборов. Он берет два элемента из разных наборов и объединяет их соответствующие наборы в один набор.
2. Найти. Определить набор, которому принадлежит элемент. Он возвращает репрезентативный элемент набора, которому принадлежит входной элемент.

Алгоритм Union-Find использует массив или древовидную структуру для представления наборов. Каждый элемент в структуре указывает на свой родительский элемент, при этом корень каждого набора указывает на себя. Алгоритм оптимизирует производительность, используя сжатие пути и объединение по рангу.

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

Вот схема высокого уровня алгоритма Union-Find:

1. Инициализируйте структуру данных с отдельными элементами, рассматриваемыми как отдельные наборы.
2. Для каждой операции Union найдите корень каждого элемента и объедините наборы, сделав один корень родителем другого.
3. Для каждой операции Find найдите корень данного элемента и верните его в качестве репрезентативного элемента набора.

Используя алгоритм Union-Find, вы можете эффективно управлять непересекающимися множествами и выполнять такие операции, как слияние множеств и поиск множества, которому принадлежит элемент.

Код на C# и Typescript

public class DisjointSets
{
    int[] parents;
    int[] weights;

    public DisjointSets(int n)
    {
       parents = new int[n];
       weights = new int[n];

       for(int i = 0 ;  i < n ; i++)
       {
           parents[i] = i;
           weights[i] = i;
       }
    }

    public void Union(int a,int b)
    {
       int rootA = Find(a);
       int rootB = Find(b);

       if(weights[rootA] > weights[rootB])
       {
          parents[rootB] = rootA;
          weights[rootA] += weights[rootB];
       }
       else
       {
          parents[rootA] = rootB;
          weights[rootB] += weights[rootA];
       }
    }

    public int Find(int a)
    {
        while( a != parents[a])
        {
            a = parents[parents[a]];
        }
        return a;
    }
}




public class Solution {
    public int EarliestAcq(int[][] logs, int n) 
    {
        DisjointSets set = new DisjointSets(n);

        Array.Sort(logs,((a,b) => {return a[0]-b[0] < 0 ? -1 : 1;}));

        int earliestTimestampWhenAllBecameFriends = 0;

        for(int i = 0 ; i < logs.Length ; i++)
        {
           int timestamp = logs[i][0];
           int a = logs[i][1];
           int b = logs[i][2];

           if(set.Find(a) != set.Find(b))
           {
               earliestTimestampWhenAllBecameFriends = timestamp;
               set.Union(a,b);
           }
        }
        
        // Code to check if at the end every person has become friends with the rest of the people.
        int parent = set.Find(0);
        for(int i = 0 ; i < n ; i++)
        {
            if(parent != set.Find(i))          
            {
              return -1;
            }
        }
        return earliestTimestampWhenAllBecameFriends;
     }
}
function earliestAcq(logs: number[][], n: number): number 
{
   const set = new DisjointSets(n);

    logs.sort((a, b) => a[0] - b[0]);

    let earliestTimestampWhenAllBecameFriends = 0;

    for (let i = 0; i < logs.length; i++) {
      const timestamp = logs[i][0];
      const a = logs[i][1];
      const b = logs[i][2];

      if (set.Find(a) !== set.Find(b)) {
        earliestTimestampWhenAllBecameFriends = timestamp;
        set.Union(a, b);
      }
    }

    // Code to check if at the end every person has become friends with the rest of the people.
    let parent = set.Find(0);
    for (let i = 0; i < n; i++) {
      if (parent !== set.Find(i)) {
        return -1;
      }
    }
    return earliestTimestampWhenAllBecameFriends;
};
class DisjointSets {
  parents: number[];
  weights: number[];

  constructor(n: number) {
    this.parents = new Array(n);
    this.weights = new Array(n);

    for (let i = 0; i < n; i++) {
      this.parents[i] = i;
      this.weights[i] = i;
    }
  }

  Union(a: number, b: number) {
    let rootA = this.Find(a);
    let rootB = this.Find(b);

    if (this.weights[rootA] > this.weights[rootB]) {
      this.parents[rootB] = rootA;
      this.weights[rootA] += this.weights[rootB];
    } else {
      this.parents[rootA] = rootB;
      this.weights[rootB] += this.weights[rootA];
    }
  }

  Find(a: number): number {
    while (a !== this.parents[a]) {
      a = this.parents[this.parents[a]];
    }
    return a;
  }
}