AcWing 4415. 点的赋值
原题链接
困难
作者:
栗子ing
,
2022-05-01 11:21:40
,
所有人可见
,
阅读 253
需要快输入,才能ac,Scanner太慢,不行
import java.io.*;
import java.util.*;
public class Main{
static int N = 300010,M = N * 2,mod = 998244353;
static int n,m,idx;
static int s1,s2;
static int[] h = new int[N],e = new int[M],ne = new int[M];
static int[] color = new int[N];
public static void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
public static boolean dfs(int u,int c){
color[u] = c;
if (c == 1) s1 ++;
else s2 ++;
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if (color[j] == 0 && !dfs(j,3 - c)) return false;
if (color[j] != 0 && color[j] == c) return false;
}
return true;
}
public static int pow2 (int sum){
int res = 1;
while (sum -- > 0){
res = res * 2 % mod;
}
return res;
}
public static void main(String[] args)throws IOException{
//Scanner scan = new Scanner(System.in);
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(bf.readLine());
while (T -- > 0){
String[] st = bf.readLine().split(" ");
n = Integer.parseInt(st[0]);
m = Integer.parseInt(st[1]);
Arrays.fill(h,1,n + 1,-1);
Arrays.fill(color,1,n + 1,0);
while (m -- > 0) {
String[] s = bf.readLine().split(" ");
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
add(a,b);add(b,a);
}
long res = 1;
for (int i = 1 ; i <= n ; i ++ ){
if (color[i] == 0){
s1 = s2 = 0;
if (dfs(i,1)) res = (long)res * (pow2(s1) + pow2(s2)) % mod;
else{
res = 0;
break;
}
}
}
System.out.println(res);
}
}
}