2017 Multi-University Training Contest - Team 4-hdu6073 Matching In Multiplication

​​題目傳送門​​

#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e5 + 1000;
const ll mod = 998244353;
int G[N],du[N],vis[N];
int tot,u,v,n,st;
ll d,ans,t1,t2;
struct Edge {
  int to;
  ll w;
  int next;
  Edge(int to_=0,ll w_=0,int next_=0):to(to_),w(w_),next(next_){}
}E[N*2];
struct node {
  int u;
  int flag;
};
void init() {
  memset(du,0,sizeof(du));
  memset(G,0,sizeof(G));
  memset(vis,0,sizeof(vis));
  tot = 1;  ans = 1;
}
inline void addEdge(int f,int t,ll dist) {
  E[tot] = Edge(t,dist,G[f]);
  G[f] = tot ++;
  E[tot] = Edge(f,dist,G[t]);
  G[t] = tot ++;
}
void topSort() {
  queue<node>Q;
  for(int i=1;i<=n;i++)
    if(du[i] == 1)
    Q.push((node){i,0});//度為1的點進行比對 
  while(!Q.empty()) {
    node now = Q.front(); 
    Q.pop();
    int u = now.u;
    if(vis[u])
    continue;
    vis[u] = 1;
    for(int i=G[u];i;i=E[i].next) {
      int v = E[i].to;
      if(vis[v])
      continue;
      du[v] --;
      //點v的度-1,因為點u會進行比對 
      if(du[v] <= 1) {
        if(!now.flag)ans = ans * E[i].w % mod;  
        Q.push((node){v,!now.flag});
      }
    }
  } 
}

void dfs(int u,int dep) {
  vis[u] = 1;
  bool flag = true;
  for(int i=G[u];i;i=E[i].next) 
  {
    int v = E[i].to;
    if(vis[v])continue;
    flag = false;
    if(dep%2)
    t1 = t1 * E[i].w % mod;
    else 
    t2 = t2 * E[i].w % mod;
    dfs(v, dep + 1);
  }
  if(flag) {
    for(int i=G[u];i;i=E[i].next) 
      if(E[i].to == st)
       {
        if(dep%2)t1 = t1 * E[i].w % mod;
        else t2 = t2 * E[i].w % mod;
      }
  }
}
int main() {
  int t; 
  scanf("%d",&t);
  while(t--) {
    init();
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
      for(int j=0;j<2;j++) {
        scanf("%d%lld",&v,&d);
        v = v + n;
        //v集合的點加上n防止和u集合的點有交集 
        du[v] ++, du[i] ++;
        //記錄每個點的度 
        addEdge(i,v,d);
      }
    }
    n = 2 * n;//(1-n)為u,(n+1-2n)為V 
    topSort();//拓撲一下，将度為1的先比對好 
    for(int i=1;i<=n;i++) {
      if(!vis[i]) {
        t1 = t2 = 1; st = i;
        /*在環上間隔着取,即st為結束點也是開始點（一個環）t1,t2(兩種方案)*/
        dfs(i,1);
        ll tmp = (t1 + t2) % mod;
        ans = ans * tmp % mod;
      }
    }
    printf("%lld\n",ans);
  }
  return 0;
}