【并查集+组合计数】ABC226 E

￡神魔★判官ぃ 2024-03-17 19:11 58阅读 0赞

[E - Just one (atcoder.jp)][E - Just one _atcoder.jp]

题意：

![06f50f3c719f4819a171a6d800ee0bc2.png][]

思路：

首先有个条件：每个点只有一个出边

如果没有直接看出结论，可以画几个链和树等特殊的图，可以发现，树是不满足条件的，环是满足条件的，因此可以初步猜想，由环和DAG组成的图是满足条件的，即把环缩点之后是个DAG，这样的图是满足条件的

然后手摸样例可知，一个图可能会有很多连通分量，每个连通分量应当满足以上条件

其实进一步，可以这么想：

![212d46c6a2254a11849c81e65b00c1d7.png][]

先去判断是否满足条件，如果一个连通分量里面点数!=边数，那么就是不满足条件的

每个连通分量都有一个环，因此每个连通分量都有2种方案

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int Inf=0x3f3f3f3f;
    const int mod=998244353;
    
    struct ty{
    	int to,next,w;
    }edge[mxe<<2];
    
    struct ty2{
    	int u,v;
    }e[mxe<<2];
    
    map<int,int> mp;
    
    int N,M,u,v;
    int tot=0;
    int head[mxn],vis[mxn];
    int F[mxn],sz[mxn];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    int find(int x){
    	return F[x]=(x==F[x])?x:find(F[x]);
    }
    void join(int u,int v){
    	int f1=find(u),f2=find(v);
    	if(f1!=f2){
    		F[f1]=f2;
    		sz[f2]+=sz[f1];
    	}
    }
    int ksm(int a,int b,int mod){
    	int res=1;
    	while(b){
    		if(b&1) res=(res*a)%mod;
    		a=a*a%mod;
    		b>>=1;
    	}
    	return res;
    }
    void solve(){
    	cin>>N>>M;
    	for(int i=1;i<=N;i++){
    		F[i]=i;
    		sz[i]=1;
    	}
    	G_init();
    	for(int i=1;i<=M;i++){
    		cin>>u>>v;
    		e[i]={u,v};
    		join(u,v);
    	}
    	for(int i=1;i<=M;i++) mp[find(e[i].u)]++;
    	for(int i=1;i<=N;i++){
    		if(sz[find(i)]!=mp[find(i)]){
    			cout<<0<<'\n';
    			return;
    		}
    	}
    	int ans=1;
    	set<int> S;
    	for(int i=1;i<=N;i++) S.insert(find(i));
    	cout<<ksm(2,S.size(),mod)<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[E - Just one _atcoder.jp]: https://atcoder.jp/contests/abc226/tasks/abc226_e
[06f50f3c719f4819a171a6d800ee0bc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7c11e2c2500d469fad3f7d62b9a9cd42.png
[212d46c6a2254a11849c81e65b00c1d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/683b1a0036184481b667903194211f00.png