글 읽기 - 질문드립니다.고수님들..예제는 맞는데 자꾸 틀려서 틀린케이스

naegeora 7년 전 0

질문드립니다.고수님들..예제는 맞는데 자꾸 틀려서 틀린케이스를 못찾겠네요...

아래는 단절점 찾는 로직대로 구현한 것입니다.

1.그래프를 DFS탐색하여 신장트리를 만들면 Tree Edge와 Non-Tree-Edge가 만들어짐.순서대로 정점번호 매김 2.한정점이 단절점이 아니려면 그정점의 모든 자손들이 자신보다 위를 가리키는 비트리간선으로 연결되어야 하고 그것이 없으면 단절점. 3. Root노드의 경우 자식이 둘이상이면 단절점이다.
int dfs(int A, bool isRoot) : A의 자식 노드가 A를 거치지 않고 도달할 수 있는 정점 중 가장 먼저 dfs함수가 방문한 정점을 반환한다.

혹시 잘못될만한 부분이나 틀린케이스 예제를 아시는 분 있으면 아려주시면 감사합니다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;


public class Main {
	static int V,E,min,counter;
	static int[] dfsorder;
	static HashSet<Integer> aplist=new HashSet<Integer>();
	static ArrayList<Integer>[] list=new ArrayList[100001];
	public static void main(String[] args) throws Exception {

		Scanner sc = new Scanner(System.in);
		V=sc.nextInt(); E=sc.nextInt();
		dfsorder=new int[V+1];
		counter=0;
		for(int i=1;i<=V;i++) {
			list[i]=new ArrayList<Integer>();	
			dfsorder[i]=0;
		}
		for(int i=0;i<E;i++){
			int a= sc.nextInt();
			int b= sc.nextInt();
			list[a].add(b); list[b].add(a); 
		}

		for(int i = 1; i <= V; i++){
			if(dfsorder[i]==0)
				dfs(i, true);
		}


		System.out.println(aplist.size()); 
		
		Iterator<Integer> iter=aplist.iterator();
		while(iter.hasNext()){
				System.out.print(iter.next()+" ");
		}
	}
	
	//A의 자식 노드가 A를 거치지 않고 도달할 수 있는 정점 중 가장 먼저 dfs함수가 방문한 정점을 반환한다.
	static public int dfs(int vertex, boolean isRoot){
		dfsorder[vertex]= ++counter;
		int ret = dfsorder[vertex];

		int child=0; //정점 A가 루트 노드 일 경우를 대비해서 DFS스패닝 트리에서의 자식 수 세어준다.
		for(int i = 0 ;  i< list[vertex].size() ; i++){
			int childvertex = list[vertex].get(i);
			if(dfsorder[childvertex]==0){//if not visited, edge tree
				child++;
				//low : 정점 A의 자식 노드가 갈 수 있는 노드중 가장 일찍 방문한 노드
				int low = dfs(childvertex, false);
				if(!isRoot && low >= dfsorder[vertex])
					aplist.add(vertex);
				ret=  Math.min(ret, low);
			}else{ //else visited, non edge tree
				ret = Math.min(ret, dfsorder[childvertex]);
			}
		}

		if(isRoot&&child >=2)aplist.add(vertex);
		return ret;
	}


}

zerozero 6년 전 0

aplist를 HashSet으로 선언하신 후 iter.next()로 출력하셨습니다.

HashSet은 요소를 추가할 때의 순서를 유지하지 않고, 가지고 있는 요소들을 정렬시켜 놓지도 않습니다.

이 문제는 단절점을 오름차순으로 출력해야 합니다.

단절점을 지닌 자료 구조로 배열이나 리스트를 사용하시고 정렬 후 출력하시면 될 것 같습니다.

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

문제

문제

출처

ICPC

질문드립니다.고수님들..예제는 맞는데 자꾸 틀려서 틀린케이스

naegeora 7년 전 0

zerozero 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말