差一点就做出来了 然而读题不太仔细…
要求是只有1个向外的边 最简单的方法就是遍历一个子图,检查它的度数和还有点的数量,如果度数是点数量的二倍,就可以达到要求。
很直觉的题
//cyc #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops") #include<bits/stdc++.h> #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,a,n) for(int i=n;i>=a;i--) #define pb push_back #define mp make_pair #define fi first #define se second #define mst(a) memset(a,0,sizeof a) using namespace std; typedef pair<int,int> pii; /* 空を眺めると そこには僕が居て */ const int maxn=2e5+5; const int maxp=1e6+5; const int mod=998244353; int vis[maxn]; int n,m; int ans; int vertexs,edges; vector<int> vec[maxn]; void dfs(int x) { edges+=vec[x].size(); vertexs++; vis[x]=1; for(int it:vec[x]) { if(!vis[it]) { dfs(it); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ans=1; cin>>n>>m; int u,v; for(int i=1; i<=m; i++) { cin>>u>>v; vec[u].pb(v); vec[v].pb(u); } for(int i=1; i<=n; i++) { vertexs=edges=0; if(!vis[i]) { dfs(i); if(vertexs*2==edges) { ans*=2; ans%=mod; } else ans=0; } } cout<<ans<<endl; }