結果
問題 | No.488 四角関係 |
ユーザー |
![]() |
提出日時 | 2017-02-24 22:42:31 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 451 ms / 5,000 ms |
コード長 | 1,960 bytes |
コンパイル時間 | 5,458 ms |
コンパイル使用メモリ | 81,512 KB |
実行使用メモリ | 53,528 KB |
最終ジャッジ日時 | 2025-01-02 23:13:51 |
合計ジャッジ時間 | 10,095 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
import java.math.BigInteger;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Comparator;import java.util.HashMap;import java.util.HashSet;import java.util.LinkedList;import java.util.Scanner;import java.util.Set;public class Main {public static long dfs(int deep, final int limit, int[] visit, boolean[] visited, ArrayList<HashSet<Integer>> adj_list){if(deep >= (limit - 1)){//System.out.println(Arrays.toString(visit));if(!adj_list.get(visit[3]).contains(visit[0])){ return 0; }if(adj_list.get(visit[0]).contains(visit[2])){ return 0; }if(adj_list.get(visit[1]).contains(visit[3])){ return 0; }if(adj_list.get(visit[2]).contains(visit[0])){ return 0; }if(adj_list.get(visit[3]).contains(visit[1])){ return 0; }//System.out.println("valid : " + Arrays.toString(visit));return 1;}else{final int curr = visit[deep];visited[curr] = true;long ret = 0;for(final int next : adj_list.get(curr)){if(visited[next]){ continue; }visit[deep + 1] = next;ret += dfs(deep + 1, limit, visit, visited, adj_list);}visited[curr] = false;return ret;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);final int N = sc.nextInt();final int M = sc.nextInt();ArrayList<HashSet<Integer>> adj_list = new ArrayList<HashSet<Integer>>();for(int i = 0; i < N; i++){adj_list.add(new HashSet<Integer>());}for(int i = 0; i < M; i++){final int a = sc.nextInt();final int b = sc.nextInt();adj_list.get(a).add(b);adj_list.get(b).add(a);}boolean[] visited = new boolean[N];int[] visit = new int[4];long answer = 0;for(int start = 0; start < N; start++){Arrays.fill(visited, false);visit[0] = start;answer += dfs(0, 4, visit, visited, adj_list);}answer /= 8;System.out.println(answer);}}