题解 P6914 【[ICPC2015 WF]Tours】

MSqwq · 2020-12-23 12:48:30 · 题解

其实这道题的关键在于找到每个简单环的边数，所以我们考虑如何处理简单环 显然，在一个简单环中，删去一条边，剩下的边就会变为割边
所以就可以得出做法：枚举原图非桥边，删去该边，处理出新增的桥边数量，所有数量 +1 的 \gcd 所有的因数即为答案

下面是代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
struct qwe{
    ll next,to,id;
}e[5020];
struct qwq{
    ll a,b;
}a[2020];
ll k=1,elast[2020];
void add(ll x,ll y,ll z)
{
    e[++k].to=y;
    e[k].next=elast[x];
    e[k].id=z;
    elast[x]=k;
}
ll dfn[2020],low[2020],tot,ans,sum;
ll v[2020],v_[2020],_v[2020];
ll gcd(ll x,ll y)
{
    return y?gcd(y,x%y):x;
}
void tarjan(ll x,ll fa)
{
    dfn[x]=low[x]=++tot;
    int qwe;
    for(int i=elast[x];i;i=e[i].next)
    {
        if(i^fa^1)
        {
            qwe=e[i].to;
            if(dfn[qwe])low[x]=min(low[x],dfn[qwe]);
            else
            {
                tarjan(qwe,i);
                low[x]=min(low[x],low[qwe]);
                if(low[qwe]>dfn[x])_v[e[i].id]=1;
            }           
        }
    }
}
void clean()
{
    k=1;
    memset(elast,0,sizeof elast);
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    memset(_v,0,sizeof _v);
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&a[i].a,&a[i].b);
        add(a[i].a,a[i].b,i);
        add(a[i].b,a[i].a,i);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
    for(int i=1;i<=m;i++)v_[i]=_v[i];
    for(int i=1;i<=m;i++)
    {
        if(v_[i]!=0||v[i]!=0)continue;
        v[i]=1,sum=1;
        clean();
        for(int j=1;j<=m;j++)
        {
            if(j!=i)
            {
                add(a[j].a,a[j].b,j);
                add(a[j].b,a[j].a,j);               
            }
        }
        for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
        for(int i=1;i<=m;i++)
        {   
            if(v_[i]==0&&_v[i]!=0)
            {
                v[i]=1;
                sum++;
            }
        }
        ans=gcd(ans,sum);
    }
    for(int i=1;i<=ans;i++)if(ans%i==0)printf("%d ",i);
}