AtCoder ABC 226E - Just one 解題心得( 題目 )
解題概念:Graph、DFS
解題方法:這題其實沒想像中的困難，題目的圖可能是很多分開的圖，假設這些子圖個別方法為A1、A2、A3 ...，則總方法數為A1*A2*A3*...，我們注意到這些子圖只有可能有2種方向，不然就是沒有(這樣答案就是0)兩種情況，而分辨方法其實很簡單，多畫幾個圖可以發現，如果這個子圖有一個環，答案就是2；如果為0或2個以上的環則無解。
注意:下方程式中的loop代表環的數量，不過因為我的算法一個環會使loop加2。
Java參考程式碼(有更好意見可留言於下方，謝謝!)
import java.io.*;
import java.util.*;
public class Main {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter bw=new PrintWriter(new OutputStreamWriter(System.out));
public static ArrayList<ArrayList<Integer>> edge=new ArrayList<>();
public static boolean[] vis=new boolean[200005];
public static int r,ret,loop,t=1;
//t:答案
public static void main(String[] args) throws Exception {
final int n=readint();
final int m=readint();
final int mod=998244353;
for(int i=0;i<=n;i++) {
edge.add(new ArrayList<Integer>());
}
int a,b;
for(int i=0;i<m;i++) {
a=readint();
b=readint();
edge.get(a).add(b);//連邊
edge.get(b).add(a);
}
for(int i=1;i<=n;i++) {
if(!vis[i]) {
loop=0;//目前環的數量
dfs(i,0);
if(loop==2) {
//如果有一個答案就*2
t*=2;
t%=mod;
}
else {
t=0;//無解
break;
}
}
}
System.out.println(t);
}
public static void dfs(int x,int pre) {
if(vis[x]) {
//如果已經拜訪代表他是環
loop++;
return;
}
vis[x]=true;
for(int i:edge.get(x)) {
if(i==pre)continue;//避免誤判
dfs(i,x);
}
}
public static int readint() throws Exception {
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
文章標籤
全站熱搜
