글 읽기 - 반례를 찾아주시면 감사하겠습니다..

ghysnzsy 3년 전 0

글에 있는 반례들 하나씩 쳐보는데 반례를 못찾았습니다..

import java.util.*;

class Node {
	public boolean visited = false;
	public int n;
	public List<Integer> line = new ArrayList<>();
	public Node(int n) {
		this.n = n;
	}
	public void sort() {
		if(line.size() > 0)
			line.sort(null);
		visited = false;
	}
	public List<Integer> searchDFS(List<Node> nodeList) {
		List<Integer> result = new ArrayList<>();
		result.add(n);
		visited = true;
		//System.out.println("line: "+line);
		for(int i = 0; i<line.size();++i) {
			if(nodeList.get(line.get(i)).visited == false) {
				result.addAll(nodeList.get(line.get(i)).searchDFS(nodeList));
			}
		}
		//System.out.println(result);
		return result;
	}
	
	public List<Integer> searchBFS(List<Node> nodeList) {
		List<Integer> result = new ArrayList<>();
		//result.add(n);
		List<Integer> resultTemp = new ArrayList<>();
		visited = true;
		for(int i = 0; i<line.size();++i) {
			if(nodeList.get(line.get(i)).visited == false) {
				result.add(line.get(i));
				nodeList.get(line.get(i)).visited =true;
			}
		}
		for(int i = 0; i<result.size();++i) {
			resultTemp.addAll(nodeList.get(result.get(i)).searchBFS(nodeList));
		}
		result.addAll(resultTemp);
		return result;
	}
}

public class Main {

    public static void main(String[] args) {
    	
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int v = scanner.nextInt();
        
        List<Node> nodeList = new ArrayList<>();
        
        for(int i =0; i<=n;++i) {
        	nodeList.add(new Node(i));
        }
        
        for(int i = 0; i<m;++i) {
        	int a = scanner.nextInt();
        	int b = scanner.nextInt();
        	nodeList.get(a).line.add(b);
        	nodeList.get(b).line.add(a);
        }
        
        for(int i =0; i<=n;++i) {
        	nodeList.get(i).sort();
        }
        
        List<Integer> resultDFS = nodeList.get(v).searchDFS(nodeList);
        
        for(int i =0; i<=n;++i) {
        	nodeList.get(i).sort();
        }
        
        List<Integer> resultBFS = nodeList.get(v).searchBFS(nodeList);
        System.out.print(resultDFS.get(0));
        for(int i = 1; i<resultDFS.size();++i)
        	System.out.print(" "+resultDFS.get(i));
        System.out.println();
        System.out.print(v);
        for(int i = 0; i<resultBFS.size();++i) {
        	System.out.print(" "+resultBFS.get(i));
        }
    }
}

ghysnzsy 3년 전 0

6 5 6

5 4

4 6

2 3

3 1

1 6

하나하나 보고 있었는데 전체 모음 글이 있어서 여기에 다시 링크 올려봅니다.
https://www.acmicpc.net/board/view/24356

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

문제

문제

출처

ICPC

반례를 찾아주시면 감사하겠습니다..

ghysnzsy 3년 전 0

ghysnzsy 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말