图割点求解问题

#include <stdio.h>
int flag[10];
int num[10];    // 记录结点的访问时间次序
int index;  // 时间
int low[10];    // 记录结点不过父结点能访问到的最早顶点

// 割点算法核心
void dfs(int cur, int father){
    // 传入参数为当前顶点编号和父顶点编号
    int child = 0;  // 记录当前结点cur的儿子个数

    num[cur] = index;   // 当前结点的访问时间
    low[cur] = index;   // 当前结点能访问到的最早顶点,开始是自己

    for (int i = 1; i <= n; i++){
        // 枚举与当前结点cur有边相连的顶点i
        if (e[cur][i] == 1){
            // 根据记录时间判断当前结点有没有被访问过
            if (num[i] == 0){
                child++;
                dfs(i, cur);    // 向下dfs
                low[cur] = min(low[cur], low[i]);   // 更新能访问的最早结点

                // 判断当前是不是割点
                if (cur != root && low[i] >= num[cur]){
                    flag[cur] = 1;
                }

                // 根结点另判
                if (cur == root && child = 2){
                    flag[cur] = 1;
                }
            }
            else if (i != father){
                // 如果结点被访问过,且不是当前结点的cur的父结点,则更新能访问的最早结点
                low[cur] = min(low[cur], num[i]);
            }
        }
    }


}


int main(){
    int n, m;
    scanf("%d%d", &n, &m);

    int e[10][10];  // 边
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            e[i][j] = 0;
        }
    }

    for (int i = 1; i <= m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        e[x][y] = 1;
        e[y][x] = 1;
    }



    index = 1;  // 初始时间为1
    dfs(1, 1);   // 从1号顶点开始进行深度优先遍历

    for (int i = 1; i <= n; i++){
        if (flag[i] == 1){
            printf("%d ", i);
        }
    }

    return 0;
}

发表评论