Проверить, содержит ли данный граф цикл (С++)

[tomsoier]

Читал несколько алгоритмов, но проблема в том, что у меня граф задан списком ребер. Все ребра хранятся в массиве структур

struct edge
    {    
    int begin;
    int weight;
    int end;
    };

Красит вершины массив paint[i]. (2 - пройдена, 1 - окрашена, 0 - не покрашена).
у меня было вот так, но это неверно

    for ( p = 0; p < l; p++ )
        {
        if (((krus[i2].begin == krus[p].begin) || (krus[i2].begin == krus[p].end) || (krus[i2].end == krus[p].end)
            || (krus[i2].begin == krus[p].begin)))
            {
            if (paint[p] == 2)
                {
                s2[p]++;
                };

            if ((paint[p] == 0) || (paint[p] == 1))
                {
                paint[p] = 1;
                };
            };
        };
    paint[i2] = 2;
    };

Массив s2[i] считает сколько раз обработанная вершина встретилась при покраске смежных вершин. Но в таком случае не получается четко по s2[i] задать условия цикла.

Помогите пожалуйста, курсач горит, как и ,пожалуй, мой мозг.

что у меня граф задан списком ребер

ну и что с того? преобразуй в списки смежности и запусти поиск в глубину

или воспользуйся структурой union-find, тогда можно и твои списки ребер ей сразу скормить без дополнительных действий (только для неорграфов)

Код:

}; }; };

что это за ***** вы нам суете? кто вас программировать учил? не ставится здесь ;

Помогите пожалуйста, курсач горит, как и ,пожалуй, мой мозг.

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

сформулируй точно вопросы, на которые ты хочешь услышать ответ.

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

также нужно сказать - граф ориентированный или нет.

[tomsoier]

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

Как реализовать dfs, если граф представлен массивом тех структур, которую я привел?

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

Какие существуют способы проверить содержит ли граф цикл?

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

для неориентированных графов есть другой вариант - вместо обхода воспользоваться структурой данных union-find aka disjoint-sets structure aka "лес непересекающихся множеств". добавляете в нее ребра по одному, каждый раз перед этим проверяете, принадлежат ли оба конца ребра одному и тому же связному множеству - если да, то в графе цикл.