글 읽기 - 반례를 못찾겠습니다;

ghdtmdwo123 4년 전 0

질문 게시판에 있는 반례들은

다통과 되는데 다른 반례은 못 찾겠네요;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Stack;

public class b2668 {

	static ArrayList succ = new ArrayList();
	static ArrayList mapcount = new ArrayList();
	static int N;
	static boolean allcheck;
	static int max = Integer.MIN_VALUE;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		int map[] = new int[101];
		//int mapcount[] = new int[N+1];
		
		
		for(int i = 1 ; i <= N; i++) {
			String temp = br.readLine();
			map[i] = Integer.parseInt(temp);
			if(i == map[i]) {
				succ.add(i);
			}
		}
		
		//boolean visited[] = new boolean[N+1];
		
		
		for(int i = 1 ; i <= N; i++) {
			
			if(i == map[i]) {
				continue;
			}
			
			boolean visited[] = new boolean[101];
			ArrayList arr1 = new ArrayList<>();
			ArrayList arr2 = new ArrayList<>();
			
			
				
			dfs(i,map,visited,arr1,arr2);
				
	
			boolean check = false;
			
			for(int j = 0; j < arr1.size(); j++) {
				
				check =	arr2.contains(arr1.get(j));
				
				if(!check) {
					break;
				}
				
			} // for문
			
			
		/*	System.out.println();
			for(int j = 0; j < arr1.size(); j++) {
				System.out.print(arr1.get(j));
			}
			System.out.println();
			for(int j = 0; j < arr2.size(); j++) {
				System.out.print(arr2.get(j));
			}
			System.out.println();
			System.out.println();
			System.out.println();*/
			
			
			
			
			if(check && max < arr1.size()) {
				allcheck = true;
				for(int m = 0; m < succ.size(); m++) {
					arr1.add(succ.get(m));
				}
				max = arr1.size();
				
				Collections.sort(arr1);
				
				mapcount =arr1;
			/*	for(int k = 0; k < arr1.size(); k++) {
					//System.out.println(arr1.get(k));
					mapcount[k] = (int) arr1.get(k);
				}*/
				
			} // if문
		
		} // for문 전체
		if(!allcheck) {
			if(succ.size() > 0) {
				System.out.println(succ.size());
				for(int i = 0; i < succ.size(); i++) {
					if(i == succ.size()-1) {
						System.out.print(succ.get(i));
					}else
					System.out.println(succ.get(i));
				}	
			}else {
				
			}
			
		}else {
			System.out.println(max);
			
			for(int i = 0; i < mapcount.size(); i++) {
				if(i == mapcount.size()-1) {
					System.out.print(mapcount.get(i));
				}else
				System.out.println(mapcount.get(i));
			}	
		}
		
		
	}
	
	static void dfs(int x1, int map[], boolean visited[],ArrayList arr1, ArrayList arr2) {
		Stack<Integer> S = new Stack(); 
		S.add(x1);
		visited[x1] = true;
		
		while(!S.isEmpty()) {
			
			int x = S.pop();
			visited[x] = true;
			//System.out.println(x + "  시작");
			arr1.add(x);
			
			if(succ.contains(map[x])) {
				continue;
			}
			
			if(!visited[map[x]]) {
			//	System.out.println(map[x] + "  추가");
				S.add(map[x]);
				arr2.add(map[x]);
			}else {
				arr2.add(map[x]);
			}
 
			
			
			
		}
		
		 
		
		
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 못찾겠습니다;

ghdtmdwo123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말