Почему DFS недостаточно быстро проверяет, является ли граф деревом

Я почти ничего не знаю о Паскале, поэтому я могу неправильно истолковать то, что вы делаете, но я думаю, что главный виновник находится в fin, где вы снимаете отметки с посещенных вершин. Это заставляет вас выполнять DFS для каждой вершины, в то время как вам нужно сделать только одну для каждого компонента.

В случае, когда имеется более одного подключенного компонента, движение либо остановится, либо

• потому что вершина указывает на уже отмеченную вершину, и в этом случае мы просто останавливаемся из-за того, что цикл был найден
• потому что вершина не указывает ни на кого (кроме самой себя), и в этом случае нам нужно найти следующую непомеченную вершину и снова запустить другую DFS оттуда

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

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

Альтернативное решение с использованием набора объединений и количества вершин/ребер

Поскольку дерево обладает свойством, согласно которому количество ребер на единицу меньше количества вершин, есть другой способ решить проблему — определить (1) компоненты связности и (2) сравнить количество ребер и вершин в каждом из них. составная часть.

Во многих языках у вас есть структура данных Set с легкодоступными методами Union/Find с почти постоянным временем. В этом случае решение простое и быстрое - почти линейное по количеству ребер.

Создайте набор для каждой вершины, представляющей ее связный компонент. Затем обработайте свой список краев. Для каждого ребра объедините множества, представленные двумя вершинами. По мере продвижения отслеживайте количество вершин в каждом наборе и количество ребер. Тот же пример:

Начальные наборы

Vertex         1  2  3  4  5
Belongs to     S1 S2 S3 S4 S5

Set            S1 S2 S3 S4 S5
Has # vertices 1  1  1  1  1
And # edges    0  0  0  0  0

Обработка края от 1 до 2

Vertex         1  2  3  4  5
Belongs to     S1 S1 S3 S4 S5

Set            S1 S3 S4 S5
Has # vertices 2  1  1  1
And # edges    1  0  0  0

Кромка обработки от 2 до 3

Vertex         1  2  3  4  5
Belongs to     S1 S1 S1 S4 S5


Set            S1 S4 S5
Has # vertices 3  1  1
And # edges    2  0  0

Кромка обработки с 3 по 4

Vertex         1  2  3  4  5
Belongs to     S1 S1 S1 S1 S5

Set            S1 S5
Has # vertices 4  1
And # edges    3  0

Обработать кромку с 4 на 1

Vertex         1  2  3  4  5
Belongs to     S1 S1 S1 S1 S5

Set            S1 S5
Has # vertices 4  1
And # edges    4  0

И мы можем остановиться здесь, потому что S1 в этот момент нарушает соотношение вершин и ребер деревьев. В S1 есть цикл. Неважно, указывает ли вершина 5 на себя или на кого-то другого.

Для потомков вот реализация в c. Давно это было, так что простите за небрежность. Он не самый быстрый, но проходит все тесты за отведенное время. Кодирование непересекающихся множеств прямо взято из псевдокода Википедии.

#include <stdio.h>

struct ds_node
{
    struct ds_node *parent;
    int rank;
};

struct ds_node v[25001];

void ds_makeSet(struct ds_node *x)
{
    x->parent = x;
    x->rank = 0;
}

struct ds_node* ds_find(struct ds_node *x)
{
    if (x->parent != x) x->parent = ds_find(x->parent);
    return x->parent;
}

int ds_union(struct ds_node *x, struct ds_node *y)
{
    struct ds_node * xRoot;
    struct ds_node * yRoot;

    xRoot = ds_find(x);
    yRoot = ds_find(y);

    if (xRoot == yRoot) return 0;

    if (xRoot->rank < yRoot->rank) 
    {
        xRoot->parent = yRoot;
    }
    else if (xRoot->rank > yRoot->rank) 
    {
        yRoot->parent = xRoot;
    }
    else 
    {
        yRoot->parent = xRoot;
        xRoot->rank++;
    }
    return 1;
}

int test(int n)
{
    int i, e, z = 0;

    for(i=1;i<=n;i++)
    {
        ds_makeSet(&v[i]);
    }
    for(i=1;i<=n;i++)
    {
        scanf("%d",&e);
        if (e)
        {
            if ( !ds_union(&v[i],&v[e]) ) 
            {
                for(i++;i<=n;i++) scanf("%d",&e);
                return 0;
            }
        }
        else
        {
            z++;
        }
    }
    return (z == 1);
}
int main()
{
    int runs; int n;

    scanf("%d", &runs);
    while(runs--)
    {
        scanf("%d", &n); 
        getc(stdin);

        test(n) ? puts("YES") : puts("NO");
    }
}