图的割点

#include<stdio.h>
#include <iostream>
#include<cmath>
#include <cctype>
#include <cstdlib>
#include<cstring>
#include<algorithm>
#include <vector>
#include<queue>

using namespace std;
#define ll long long
#define il inline
#define oo (2147000000)
#define sc(x) scanf("%d",&x)
#define scc(x, y) scanf("%d%d",&x,&y)
#define sccc(x, y, z) scanf("%d%d%d",&x,&y,&z)
#define p(x) printf("%d\n",x)
#define m(x, y) ((x+y)>>1)
#define l(x) (x<<1)
#define r(x) (x<<1|1)
const int maxn = 1e5 + 6;

int u[100], v[100], nextt[100], first[100];
int m, n, root;
//num记录每个顶点的时间戳，low记录每个顶点在不经过父顶点能够回到的最小时间戳
//flag用来标记是不是割点
int num[100], low[100], index, flag[100];

void dfs(int cur, int fa) {//传入两个参数，当前节点和父节点的编号
    int child = 0, i, k;//child用来记录在生成树中当前顶点cur的儿子个数

    index++;
    num[cur] = index;//当前顶点的时间戳
    low[cur] = index;//当前顶点能访问到的最早的时间戳
    k = first[cur];
    while (k != -1) {
        i = v[k];
        if (num[i] == 0) {//如果顶点i的时间戳为0，说明顶点i还没有被访问过
            child++;
            dfs(i, cur);
            //更新当前顶点cur能访问到最早的时间戳
            low[cur] = min(low[cur], low[i]);
            //如果当前顶点不是根节点并且满足low[i]>=num[cur],则当前顶点为割点
            if (cur != root && low[i] >= num[cur])
                flag[cur] = 1;
            if (cur == root && child == 2)
                flag[cur] = 1;
        } else if (i != fa) {
            //如果顶点曾经被访问过，并且不是cur的父亲，说明此时的i为cur的祖先
            //需要更新时间戳
            low[cur] = min(low[cur], num[i]);
        }
        k = nextt[k];
    }
}


int main() {
    int i;

    scc(n, m);
    for (i = 1; i <= n; i++)
        first[i] = -1;

    for (i = 1; i <= m; i++) {//读入m条边
        scc(u[i], v[i]);
    }

    for (i = m + 1; i <= 2 * m; i++) {
        u[i] = v[i - m];
        v[i] = u[i - m];
    }

    for (i = 1; i <= 2 * m; i++) {
        nextt[i] = first[u[i]];
        first[u[i]] = i;
    }
    root = 1;
    dfs(1, root);
    for (i = 1; i <= n; ++i) {
        if (flag[i] == 1)
            p(i);
    }
    return 0;
}

图的割边

#include<stdio.h>
#include <iostream>
#include<cmath>
#include <cctype>
#include <cstdlib>
#include<cstring>
#include<algorithm>
#include <vector>
#include<queue>

using namespace std;
#define ll long long
#define il inline
#define oo (2147000000)
#define sc(x) scanf("%d",&x)
#define scc(x, y) scanf("%d%d",&x,&y)
#define sccc(x, y, z) scanf("%d%d%d",&x,&y,&z)
#define p(x) printf("%d\n",x)
#define m(x, y) ((x+y)>>1)
#define l(x) (x<<1)
#define r(x) (x<<1|1)
const int maxn = 1e5 + 6;

int u[100], v[100], nextt[100], first[100];
int m, n, root;
//num记录每个顶点的时间戳，low记录每个顶点在不经过父顶点能够回到的最小时间戳
//flag用来标记是不是割点
int num[100], low[100], index;

void dfs(int cur, int fa) {//传入两个参数，当前节点和父节点的编号
    int i, k;

    index++;
    num[cur] = index;//当前顶点的时间戳
    low[cur] = index;//当前顶点能访问到的最早的时间戳
    //找到与cur相连的顶点i
    k = first[cur];
    while (k != -1) {
        i = v[k];
        if (num[i] == 0) {//如果顶点i的时间戳为0，说明顶点i还没有被访问过
            dfs(i, cur);
            //更新当前顶点cur能访问到最早的时间戳
            low[cur] = min(low[cur], low[i]);
            if (low[i] > num[cur])
                printf("%d-%d\n", cur, i);
        } else if (i != fa) {
            //如果顶点曾经被访问过，并且不是cur的父亲，说明此时的i为cur的祖先
            //需要更新时间戳
            low[cur] = min(low[cur], num[i]);
        }
        k = nextt[k];
    }
}

int main() {
    int i;

    scc(n, m);
    for (i = 1; i <= n; i++)
        first[i] = -1;

    for (i = 1; i <= m; i++) {//读入m条边
        scc(u[i], v[i]);
    }

    for (i = m + 1; i <= 2 * m; i++) {
        u[i] = v[i - m];
        v[i] = u[i - m];
    }

    for (i = 1; i <= 2 * m; i++) {
        nextt[i] = first[u[i]];
        first[u[i]] = i;
    }
    root = 1;
    dfs(1, root);

    return 0;
}