eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ещё одна задача про деревья

Ещё одна задача про деревья

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Есть граф из N вершин. Изначально он пустой. Нужно обработать M запросов:

  • добавить ребро из вершины v_1 в вершину v_2, при этом вершины v_1 и v_2 находятся в разных деревьях и вершина v_2 является корнем какого-то дерева.

  • по двум вершинам a и b определить, лежат ли они в одном дереве.

Решение задачи

Реализуем СНМ с эвристикой сжатия путей:

int n, m, l[NMAX];
int calc_leader (int v)
{
    if (l[v] != v)
        l[v] = calc_leader (l[v]);
    return l[v];
}

int main()
{
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
        l[i] = i;
    for (int i = 1; i <= m; i ++)
    {
        int x, y, z;
        scanf ("%d%d%d", &z, &x, &y);
        if (z == 1)
            l[y] = x;
        else
            if (calc_leader (x) == calc_leader (y))
                printf ("YES\n");
            else
                printf ("NO\n");
    }
}

Вам же предстоит сделать тест, на котором это решение будет работать долго. Более точно, нужно сделать тест, на котором количество вызовов функции calc_leader будет не меньше, чем 1/4 M log_2 M.

Giriş verilənləri

Входной файл содержит два целых числа N и M (1 ≤ N ≤ 10^6, 1 ≤ M ≤ 10^5, M ≤ N).

Çıxış verilənləri

Выведите M строк. i-ая строка должна иметь вид 1\ x\ y, если i-ый запрос заключается в добавлении ребра из вершины x в вершину y, или 0\ x\ y, если спрашивается, лежат ли вершины x и y в одном дереве.

Nümunə

Giriş verilənləri #1
2 2
Çıxış verilənləri #1
1 2 1
0 1 1