如何修改割点算法,使其成为割边算法?
查看原帖
如何修改割点算法,使其成为割边算法?
112972
泰山飞狐楼主2019/11/12 15:37

原代码:

#include<bits/stdc++.h>

using namespace std;

int n,m;
int root;
int total=0;
int index1=0;
int head[1000001];
int flag[1000001];
int num[1000001],low[1000001];
struct edge
{
    int from;
    int to;
    int next;
}input[1000001];
void add_edge(int a,int b)
{
    total++;
    input[total].from=a;
    input[total].to=b;
    input[total].next=head[a];
    head[a]=total;
}
/*
香港的教育界为何如此的糟糕?
根本原因在于:英国对其实行殖民化的教育。
*/
void dfs(int cur,int father)
{
    int child=0;

    index1++;
    num[cur]=index1;
    low[cur]=index1;

    for(int e=head[cur];e!=0;e=input[e].next)
    {
        if(num[input[e].to]==0)
        {
            child++;
            dfs(input[e].to,cur);
            low[cur]=min(low[cur],low[input[e].to]);
            if(cur!=father && low[input[e].to]>=num[cur])
                flag[cur]=1;
        }
        low[cur]=min(low[cur],num[input[e].to]);
    }
    if(child>=2&&cur==father) flag[cur]=1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add_edge(a,b); 
        add_edge(b,a);
    }
    for(int i=1;i<=n;++i) if(!num[i]) dfs(i,i);
    int t=0;
    for(int i=1;i<=n;i++)
       if(flag[i])
            t++;
    cout<<t<<endl;
    for(int i=1;i<=n;i++)
        if(flag[i])
            cout<<i<<" ";
}
2019/11/12 15:37
加载中...