还是关于求图割点的问题

litianhua

啊哈算法里给出的是用邻接矩阵存储的图，有没有用邻接表写的代码来看看？就是书里给出的那种不用指针而是使用数组的方法来实现邻接表的代码？

CommandCraft

[mw_shl_code=c,true]#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100005

int head[maxn]={0}; int vis[maxn]={0}; int lowdex[maxn]={0};
int idx = 0; int book[maxn]={0};
struct edge {
    int v, next;
} edges[2*maxn]; int tail;
int add_edge(int u, int v) {
    edges[++tail].v=v;
    edges[tail].next=head;
    head=tail;
} int n, m; int cnt=0;
int dfs(int u, int fa) {
    int ch = 0;
    vis=++idx;
    lowdex=idx;
    for (int i = head; i; i=edges.next) {
        if (!vis[edges.v]) {
            ch++;
            dfs(edges.v, u);
            lowdex=std::min(lowdex,  lowdex[edges.v]);
            if (lowdex[edges.v]>=vis) {
                if (book==0) cnt++;
                book=1;
            }
        } else if (edges.v!=fa) {
            lowdex=std::min(lowdex, vis[edges.v]);
        }
    }if (fa==-1&&ch==1) {
        if (book==1) cnt--;
            book=0;
    }
}
int main() {
    int a, b;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &a, &b);
        add_edge(a, b);
        add_edge(b, a);
    } memset(vis, 0,sizeof(vis));
    for (int i=1;i<=n;i++){
        if (!vis) dfs(i,-1);
    }printf("%d\n", cnt);
    for(int i = 1; i <= n; ++i) {
        if (book) printf("%d ", i);
    }
    return 0;
}
[/mw_shl_code]

链式前向星存图

litianhua

CommandCraft 发表于 2018-3-30 22:50
[mw_shl_code=c,true]#include
#include
#include

谢谢，我研究下啊，多谢费心