hdu6736（寻找最小环）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6736

题意：

在给定图中寻找所有最小环

保证不存在一条边经过两个简单环

数据范围：

$1\leq n \leq 300 000$

$1\leq m \leq 500 000$

分析：

每次遍历到某个点时入栈，遍历结束时出栈

依次把点加入栈中，如果下一个点在栈中，那么这里肯定构成了一个简单环

只需要计算栈中到达下一点元素的数量就行，不需要出栈

比赛的时候没想到这个方法，队友给出正确思路，但是实现时没写好，背锅

AC代码：

#include<bits/stdc++.h>

#define ll long long

#define pic pair<int,char>

using namespace std;

const int maxn=3e5+7;

const int mod= 998244353;

vector<int>ve[maxn];

int ins[maxn],top,sk[maxn],n,m,vis[maxn];

ll ans=1;

ll qpow(int a,int b){

    ll res=1,k=a;

    while(b){

        if(b&1)res=res*k%mod;

        k=k*k%mod;

        b/=2;

    }

    return res;

}

void dfs(int x,int f){

    sk[++top]=x;

    ins[x]=1;

    vis[x]=1;

    for(int i=0;i<ve[x].size();i++){

        int v=ve[x][i];

        if(vis[v]==0){

            dfs(v,x);

        }else if(v!=f&&ins[v]){

            int res=1;

            int zz=top;

            while(1){

                zz--;

                res++;

               // cout<<zz<<endl;

                if(sk[zz]==v)break;

            }

            if(res){

               // cout<<res<<endl;

                m-=res;

                ans=(qpow(2,res)-1+mod)%mod*ans%mod;

            }

        }

    }

    ins[sk[top]]=0;

    --top;

}

int main(){

   // cout<<qpow(2,10)<<endl;

    while(scanf("%d %d",&n,&m)==2){

        for(int i=1;i<=n;i++)ve[i].clear();

        top=0;

        memset(ins,0,sizeof(ins));

        memset(vis,0,sizeof(vis));

        for(int i=1;i<=m;i++){

            int a,b;

            scanf("%d %d",&a,&b);

            ve[a].push_back(b);

            ve[b].push_back(a);

        }

        for(int i=1;i<=n;i++){

            if(vis[i]==0){

                dfs(i,0);

            }

        }

        ans=qpow(2,m)*ans%mod;

        printf("%lld\n",ans);

        ans=1;

    }

    return 0;

}

/*

7 9

1 2 1 3 2 3 3 4 4 5 5 3 3 6 3 7 6 7

*/

巴特西

hdu6736（寻找最小环）

题目链接：

题意：

数据范围：

分析：

AC代码：

最新文章

热门文章