글 읽기 - 어떤 케이스에서 틀린건지 모르겠네요 ㅠㅠ

filot 6년 전 0

예제는 잘 통과하는데

올리면 4%에서 fail이네요 ㅠㅠ 어떤 케이스가 잘못된건지 조언을 해주실 분 있나요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int V;
    static int E;
    static int order;
    static List[] adjList;
    static List<Edge> cutList;
    static int[] discovered;

    public static void main(String[] args) throws Exception {        
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        StringTokenizer st = new StringTokenizer(reader.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        discovered = new int[V + 1];
        adjList = new List[V + 1];
        cutList = new ArrayList<Edge>();

        for (int i = 1; i <= V; i++)
            adjList[i] = new ArrayList<Integer>();

        for (int i = 1; i <= E; i++) {
            st = new StringTokenizer(reader.readLine());

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            adjList[u].add(v);
            adjList[v].add(u);
        }

        for (int i = 1; i <= V; i++)
            if (discovered[i] == 0)
                dfs(1, 0);

        int count = cutList.size();
        writer.println(count);

        Collections.sort(cutList, new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return Integer.compare(o1.u, o2.u);
			}
		});

        for (Edge each : cutList)
        	writer.println(each);

        writer.close();
        reader.close();
    }

    public static int dfs(int u, int parent) {
        discovered[u] = ++order;
        int num = discovered[u];

        List<Integer> list = adjList[u];

        for (Integer v : list) {
        	if (v == parent)
        		continue;

            if (discovered[v] == 0) {
                int low = dfs(v, u);

                if (low > discovered[u])
                	cutList.add(new Edge(Math.min(u, v), Math.max(u, v)));

                num = Math.min(num, low);
            }
            else {
                num = Math.min(num, discovered[v]);
            }
        }

        return num;
    }
}

class Edge {
	int u;
	int v;

	public Edge(int u, int v) {
		this.u = u;
		this.v = v;
	}

	@Override
	public String toString() {
		return u + " " + v;
	}
}

zlzmsrhak 6년 전 2

간선을 정렬할 때, 사전순 정렬이기 때문에 u가 같은 경우 v를 비교해야 합니다.

filot 6년 전 0

아.. 그러 ㄴ케이스가 빠졋군요.. 정렬 순서를 좀더 잡아 주었어야했네요~

감사합니다.

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

문제

문제

출처

ICPC

어떤 케이스에서 틀린건지 모르겠네요 ㅠㅠ

filot 6년 전 0

zlzmsrhak 6년 전 2

filot 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말