Блог пользователя Easy_

Наименьший общий предок
Автор Easy_, 10 лет назад, По-русски

Господа кодфорцесеры, вот задачка: Расследование

Решаю самым банальным алгоритмом так:

#include <fstream>

#define LL long long
#define MAXN 1e6 + 1

using namespace std;

fstream in("input.txt"), 
		out("output.txt", std::ios::out);

int G[101][101], N, t, i, k;

int Parent(int u)
{
	if(u-- == 1)
		return 1;
	int _t = 0;
	for(; !G[u][_t]; _t++);
	return _t + 1;
}

int Depth(int u)
{
	int k = 0;
	while(u != 1) 
		u = Parent(u), k++;
	return k;
}

int main()
{
	for(in >> N >> _a >> _b; in >> t; i++)
		G[t - 1][i + 1] = G[i + 1][t - 1] = 1;
	
	int ha = Depth(_a), hb = Depth(_b);

	while(ha != hb)
		if(ha > hb)
			_a = Parent(_a), ha--;
		else
			_b = Parent(_b), hb--;
	
	while(_a != _b)
		_a = Parent(_a), _b = Parent(_b);

	out << _a;

	return 0;
}

Сложность O(h)

но получаю TL в 11 тесте, хотя максимальное значение h 29999

вроде не должно TL давать. Подскажите пожалуйста в чем проблема?

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

int G[101][101] — при N<=30000 это не самая удачная идея. Нужно хранить граф иначе — списками смежности, или банально предками, как во входных данных.

А так у нас, во-первых, выход за пределы массива (и ML при нормальном размере массива), во вторых — сложность N^2 вместо N.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо всем большое))

    Хотел бы узнать а почему сложность O(N*N) ?

    Разве не O(H) ? H — максимальная высота дерева.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ниже proVIDec уже написал. Пускай у нас есть граф вида 1->2->3->4->...->n. Тогда при вызове Depth(N) сначала будет n-1 операция в Parent(n), из-за цикла for(; !G[u][_t]; _t++);, потом еще n-2 операции в Parent(n-1), и так далее вверх по цепочке.

      Нету смысла усложнять себе жизнь, и если значение parent[x] дано во входных данных — можно его сохранить в массив, и возвращать за О(1), а не перебирать.

      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

1) int G[101][101] Эмм... N ≤ 30000

2) int Parent(int u) работает за O(N)

3) int Depth(int u) вызывает int Parent(int u) O(N) раз.

4) Итого int Depth(int u) работает за O(N2)

Вывод: хранить граф списком смежности, то есть vector<int> G[MAXN].

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    спасибо, никогда не сталкивался с этим, не хранил граф никак, кроме матрицы смежности, хотел бы узнать, а как они(смежные вершины) будут храниться в списке? придется ли алгоритмы переписывать?

    Я сделал таким образом:

            vector<int> G[MAXN];
	in >> N;

	for(int x = 0; x < N; x++)
		for(int y = 0; y < N; y++)
			G[x].push_back(0);

	for(in >> _a >> _b; in >> t; i++)
		G[t - 1][i + 1] = G[i + 1][t - 1] = 1;

    Но уверен, что не правильно, это та же матрица смежности :D

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      В G[v] хранятся все смежные с v вершины.

      Если придерживаться Вашего стиля:

      vector<int> G[MAXN];
	in >> N;

	for(in >> _a >> _b; in >> t; i++)
		G[t - 1].push_back(i + 1);

      Хотя мне кажется, что где-то тут  ± 1-error :)

      Если не заморачиваться, то vector хранит только добавленные элементы (на самом деле это почти так), то есть список смежности будет занимать O(M) памяти, где M — количество ребер.

      Теперь для данной вершины вместо перебора всего ряда в матрице смежности, нужно перебирать вершины из списка этой вершины.

      → Ответить
»
10 лет назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Можно решить не используя вектор.

Решение: Давайте сделаем массив p[], где p[x] — предок вершины x. И наибольший общий предок можно найти втупую, находишь всех предков X за O(h), помечаешь их в массиве used, а потом среди предков Y находишь отмеченную в used. В общем, примерно так:

scanf("%d%d%d", &n, &x, &y);
for (int i = 2; i <= n; i++)
   scanf("%d", &p[i]);
 
p[1] = 1;
while (p[x] != x) {
    u[x] = true;
    x = p[x];
}
while (p[y] != y) {
    if (u[y]) {
        printf("%d", y);
        return 0;
    }
    y = p[y];
}
printf("1");
→ Ответить