C++无向图割点模版，求调

Question

割点模版，求调

#include<bits/stdc++.h>
using namespace std;
#define MAXN 20010
int n,m,dfn[MAXN],low[MAXN],cnt,idx,deg[MAXN],ans;
int st[MAXN],top;
vector<int> g[MAXN];
vector<int> vdcc[MAXN];
map<int,int> mp;
void dfs(int u,int fa){
    dfn[u]=low[u]=++cnt;
    st[++top]=u;
    for(int v:g[u])
        if(v!=fa){
            if(!dfn[v]){
                dfs(v,u);
                low[u]=min(low[u],low[v]);
                if(low[v]>=dfn[u]){
                    vdcc[++idx].push_back(u);
                    ++deg[u];
                    while(true){
                        int vv=st[top--];
                        vdcc[idx].push_back(vv);
                        ++deg[vv];
                        if(vv==v)break;
                    }
                }
            } else
                low[u]=min(low[u],dfn[v]);
        }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]){
            dfs(i,-1);
            top=0;
        }
    for(int i=1;i<=n;i++)
        ans+=deg[i]>1;
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
        if(deg[i]>1)
            printf("%d\n",i);
    return 0;
}

Answer 1

让 “紫雾凌寒” 来帮你回答,本回答结合 DeepSeek

如果还有问题，请评论或点击头像私信，如果有帮助到您, 请关注、采纳、点赞

1. 关键点分析：
   - 这段代码是用于求解无向图割点的模板代码，但不完整。
   - dfn[MAXN]数组用于记录节点的深度优先搜索（DFS）序，low[MAXN]数组用于记录节点能追溯到的最早的DFS序。
   - 目前代码缺少对low数组的定义以及后续核心的DFS求解割点的逻辑。
2. 解决方案：
   - 首先补充完整代码，定义low数组并实现DFS函数来求解割点。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 20010
int n,m,dfn[MAXN],low[MAXN];
bool cut[MAXN];
int timestamp;

void dfs(int u, int fa) {
    dfn[u]=low[u]=++timestamp;
    int child = 0;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!dfn[v]) {
            dfs(v, u);
            low[u]=min(low[u], low[v]);
            if (low[v] >= dfn[u] && fa!=-1) {
                cut[u]=true;
            }
            child++;
        } else if (v!=fa) {
            low[u]=min(low[u], dfn[v]);
        }
    }
    if (fa == -1 && child == 1) {
        cut[u]=false;
    }
}

void find_cut_points() {
    timestamp = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(cut, false, sizeof(cut));
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            dfs(i, -1);
        }
    }
}

这里假设图的邻接表存储方式为vector<int> G[MAXN];，并且在使用前需要根据输入构建好邻接表。

1. 多种解决方案的优缺点：
   - 深度优先搜索（DFS）方法：
   • 优点：直观易懂，能够有效地利用DFS序和回溯的性质来找到割点。
   • 缺点：时间复杂度为(O(n + m))，对于大型图可能效率较低。
2. 总结：
   - 上述代码实现了通过DFS来求解无向图割点的功能。首先定义了必要的数组，然后通过DFS遍历图，利用dfn和low数组的性质判断每个节点是否为割点。在实际使用时，需要先构建好图的邻接表，再调用find_cut_points函数来求解割点。

需要注意的是，完整的程序还需要根据具体的输入格式来读取图的边信息并构建邻接表。

希望以上解答对您有所帮助。如果您有任何疑问，欢迎在评论区提出。