ABCDE

https://www.acmicpc.net/problem/13023

13023번: ABCDE

 

// 코드

import java.util.*;
import java.io.*;
 
public class Main{
  
  public static boolean flag = false;
  
  public static void getResult(int x, int N, int M, List<ArrayList<Integer>> listGraph, int[]check, int idx) {
    if(flag) return;
    
    if(idx >= 5) {
      flag = true;
    } else {
      for(int j=0; j<listGraph.get(x).size(); j++) {
        if(check[listGraph.get(x).get(j)] == 0) {
          check[listGraph.get(x).get(j)] = 1; 
          getResult(listGraph.get(x).get(j), N, M, listGraph, check, idx+1);
          check[listGraph.get(x).get(j)] = 0; 
        }
        
      }
    } 
    
  }
  
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    
    int[] result = new int[N];
    int[] check  = new int[N];
    
    // 1.인접리스트를 구한다.
    List<ArrayList<Integer>> listGraph = new ArrayList<>();;
    for(int i=0; i<N; i++) {
      listGraph.add(new ArrayList<Integer>()); 
    }
    for(int i=0; i<M; i++) {
      st = new StringTokenizer(br.readLine());
      int x = Integer.parseInt(st.nextToken());
      int y = Integer.parseInt(st.nextToken());
      
      listGraph.get(x).add(y);
      listGraph.get(y).add(x);
    } 
    
    // 2.DFS 탐색을 하여 깊이가 4이상이면 1, 아니면 0을 출력한다.
    for(int i=0; i<N; i++)
      getResult(i, N, M, listGraph, check, 0);
    
    if(flag) {
      System.out.println(1);  
    } else {
      System.out.println(0);
    }
    
  }
}