题目链接 CCPC2019 F题.

题意：Give a cactus tree,Let you find the number of sides of each small ring,It can be solved with fast powers.

思路：第一反应是tanjar乱搞,Take the dots out of each ring,Similar to the method of shrinking points.But suddenly feltdfs能做,Because of the special nature of cactus,That is, there will be no more than one branch on a ring.

So first we start from any point,dfsGo down to record depth and mark,When we reach a point marked off and the depth is less than the current point,Prove that we just walked a circle,Then the depth difference between the two points+1is the number of sides of the ring,What if the depth of the mark is greater than the depth of the current point,In fact, this is the ring we have dealt with before,Just skip it,就这样就完了.

dfs代码：

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
typedef unsigned long long ull;
typedef long long ll;
#define pii make_pair
#define pr pair<int,int>
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const int mod=998244353;
const int maxn=3e5+5;
const int maxm=1e6+5;
struct node
{
    int to,p;
}edge[maxm];
int head[maxn],sign;
int vis[maxn];
int n,m;
ll res;
ll qmod(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll qqmod(ll a,ll b)
{
    ll ans=qmod(a,b);
    ans=(ans-1+mod)%mod;
    return ans;
}
void init()
{
    for(int i=0;i<=n;i++) head[i]=-1,vis[i]=0;
    sign=0;
}
void add(int u,int v)
{
    edge[sign]=node{v,head[u]};
    head[u]=sign++;
}
void dfs(int u,int cnt)
{
    vis[u]=cnt;
    for(int i=head[u];~i;i=edge[i].p)
    {
        int v=edge[i].to;
        if(vis[v])
        {
            if(vis[u]-vis[v]>1)//Determine whether the parent node is gone
            {
                ll c=vis[u]-vis[v]+1;
                res=res*qqmod(2,c)%mod;
                m-=c;
            }
        }
        else dfs(v,cnt+1);
    }
}
int main()
{
    int x,y;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(m==0)
        {
            puts("0");
            continue;
        }
        init();
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&x,&y);
            add(x,y),add(y,x);
        }
        res=1;
        dfs(1,1);
        res=res*qmod(2,m)%mod;
        printf("%lld\n",res);
    }
    return 0;
}

然后就是tanjar的做法.

In fact, many people do this question with a double point, I don't think it is necessary,And what I write keeps timing out（-.-

问题在于tanjarTo find the Unicom component is actually to find a large ring,The second example is actually a large connected component

But the idea is probably the same,Also as a review.

当我们tanjar到一个点low[v]>=low[u]证明uA point is a cut point,The way we shrink the point is to put stackmedium until equal touAll points are taken out

Here is until equalsvJust take out all the points,然后+1is the block（The block description should be fine）The quantity is obtained,

Only the number of blocks is greater than 2Just a ring

代码是T的,不晓得为啥~（Hope you guys can help！

//#pragma comment (linker, "/STACK:102400000,102400000")
//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
typedef unsigned long long ull;
typedef long long ll;
#define pii make_pair
#define pr pair<int,int>
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const int mod=998244353;
const int maxn=3e5+5;
const int maxm=1e6+5;
struct node
{
    int to,p;
}edge[maxm];
int head[maxn],sign;
int n,m;
int Stack[maxn],low[maxn],dfn[maxn];
int num[maxn];
int top,t,cnt;
ll p[maxn],r[maxn];
ll res;
ll qmod(ll a,ll b)
{
    if(r[b]) return r[b];
    int c=b;
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return r[c]=ans;
}
ll qqmod(ll a,ll b)
{
    if(p[b]) return p[b];
    ll ans=qmod(a,b);
    ans=(ans-1+mod)%mod;
    return p[b]=ans;
}
void init()
{
    t=top=cnt=sign=0;
    for(int i=1;i<=n;i++)
    {
        low[i]=dfn[i]=0;
        head[i]=-1;
    }
}
void add(int u,int v)
{
    edge[sign]=node{v,head[u]};
    head[u]=sign++;
}
void tanjar(int u,int pre)
{
    dfn[u]=low[u]=++t;
    Stack[++top]=u;
    for(int i=head[u];~i;i=edge[i].p)
    {
        int v=edge[i].to;
        if(v==pre) continue;
        if(!dfn[v])
        {
            tanjar(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                cnt++;
                num[cnt]=0;
                int x;
                do{
                    x=Stack[top--];
                    num[cnt]++;
                }while(x!=v);
                num[cnt]++;
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(m==0) {puts("0");continue;}
        init();
        int x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&x,&y);
            add(x,y),add(y,x);
        }
        res=1;
        for(int i=1;i<=n;i++)
            if(!dfn[i]) tanjar(i,i);
        for(int i=1;i<=cnt;i++)
            if(num[cnt]>=3) res=res*qqmod(2,num[cnt])%mod,m-=num[cnt];
        res=res*qmod(2,m)%mod;
        printf("%lld\n",res);
    }
}