Использование обхода в глубину для поиска точек сочленения графа

Question

Попробовал сделать функцию для поиска точек сочленения графа через обход в глубину, весь интернет перекопал, но так и не смог интерпретировать это на СИ, получился такой код,вроде верный, но точки он не ищет, можете подсказать что может быть не так? Массив Matrix это изначальный массив графа где указаны связи. matrix имеет вид

0 1 0 1 0 0
1 0 1 1 0 0
0 1 0 0 0 0
1 1 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0

и функция должна выводить 2 и 4

int time, tin[100], up[100], visit[100], count;
 
void dfs (int v, int p) {
    time++;
    visit[v] = 1;
    tin[v] = time;
    up[v] = time;
    count = 0;
    
    for (int i = 0; i < n; i++) {
        int to = matrix[v][i];
        if (to == p)  continue;
        if (visit[to] == 1)
            if (up[v] > tin[to]) up[v] = tin[to];
        else {
            dfs (to, v);
            count++;
            if (up[v] > up[to]) up[v] = up[to];
            if (up[to] >= tin[v] && p != -1)
                printf("%d", v);
        }
    }
    if (p == -1 && count > 1)   printf("%d", v);
} 

void findCutPoints(){
    for (int i = 0; i < n; i++){
        if  (visit[i] != 1){
            dfs(i, -1);
        }
    }
}

Answer 1

Это код с емакса. Однако вы используете его с матрицей, а не со списками смежности, и не учли этого - в to надо заносить номер смежной вершины, а не наличие ребра.

Я подправил начало цикла, теперь выводит 1 3 (2 и 4 при нумерации с единицы), и логику ифов, но, видимо, чего-то ещё не заметил, и ещё и 0 добавляет.

int timer, tin[100], up[100], visit[100], count, n=6;
int matrix[6][6] = 
   {{0, 1, 0, 1, 0, 0},
    {1, 0, 1, 1, 0, 0},
    {0, 1, 0, 0, 0, 0},
    {1, 1, 0, 0, 1, 1},
    {0, 0, 0, 1, 0, 1},
    {0, 0, 0, 1, 1, 0}};

void dfs(int v, int p) {
    visit[v] = 1;
    timer++;
    tin[v] = timer;
    up[v] = timer;
    count = 0;

    for (int i = 0; i < n; i++) {
        if (matrix[v][i]==0 || i==v)
            continue;
        int to = i;
        if (to == p)  continue;
        if (visit[to] == 1) {
            if (up[v] > tin[to])
                up[v] = tin[to];
        }
        else{
                dfs(to, v);
                if (up[v] > up[to]) up[v] = up[to];
                if (up[to] >= tin[v] && p != -1)
                    printf("%d", v);
                count++;
        }
    }
    if (p == -1 && count > 1)   printf("%d", v);
}

void findCutPoints() {
    for (int i = 0; i < n; i++) {
        if (visit[i] != 1) {
            dfs(i, -1);
        }
    }
}

int main()
{
    findCutPoints();
}

БЛОГ НА HUSL

Использование обхода в глубину для поиска точек сочленения графа

Ответы (1 шт):