Ещё одна задача про деревья
Ещё одна задача про деревья
Есть граф из 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ə
2 2
1 2 1 0 1 1