那么剩下的图中左右各有m个点，每个点度数都不小于2，且左边每个点度数都是2，而右侧总度数是2m，因此右侧只能是每个点度数都是2。这说明这个图每个连通块是个环，在环上间隔着取即可，一共两种方案。
时间复杂度O(n)。
#include<iostream> #include<stdio.h> #include<vector> using namespace std; typedef long long ll; const int maxn=6e5+10; const int mod=998244353; struct edge{ int v;ll w; }; int t,n,cnt,d[maxn],q[maxn]; bool vis[maxn]; ll ans,tmp[2]; vector<edge> e[maxn]; void dfs(int u,int flag,int f){ for(int i=0;i<e[u].size();i++){ int v=e[u][i].v; if(!vis[v]&&v!=f){ vis[v]=1; tmp[flag]=(tmp[flag]*e[u][i].w)%mod; dfs(v,flag^1,u); } } } int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); ans=1;cnt=0; for(int i=1;i<=2*n;i++) e[i].clear(),d[i]=0,vis[i]=0; for(int i=1;i<=n;i++){ int v1,v2;ll w1,w2; scanf("%d%lld%d%lld",&v1,&w1,&v2,&w2); e[i].push_back({v1+n,w1}); e[i].push_back({v2+n,w2}); e[v1+n].push_back({i,w1}); e[v2+n].push_back({i,w2}); d[i]+=2,d[v1+n]++,d[v2+n]++; } for(int i=n;i<=2*n;i++) if(d[i]==1) q[cnt++]=i,vis[i]=1; int cur=0; while(cur<cnt){ int u=q[cur++]; for(int i=0;i<e[u].size();i++){ int v=e[u][i].v; if(!vis[v]){ ans=(ans*e[u][i].w)%mod; vis[v]=1; for(int j=0;j<e[v].size();j++) if(--d[e[v][j].v]==1) q[cnt++]=e[v][j].v,vis[e[v][j].v]=1; } } } //printf("%d\n",ans); for(int i=1;i<=n;i++) if(!vis[i]) tmp[0]=tmp[1]=1,dfs(i,1,-1),ans=(ans*(tmp[0]+tmp[1]))%mod; printf("%lld\n",ans); } }