글 읽기 - 반례를 도저히 찾을 수가 없습니다 ㅜㅜ

chldntjr1211 5년 전 0

질문게시판에 나온 반례 이외에도 스스로 꽤 오래.. 만들어봤지만 찾지 못했습니다. 대부분의 경우 정답을 내놓더군요;;
로직은 SCC 알고리즘으로 sccId 배열에 각 속하는 그룹의 번호를 저장하고
나중에 각 노드들을 그룹번호로 묶어 다시 memoization dfs를 통해 최대 감염 수를 찾고 
최대감염 수를 가지는 모든 노드들을 출력하는 식입니다. 
도와주떼엽 ㅠ

    static int n;
    static List<List<Integer>> adj;
    static int[] sccId, discovered;
    static Stack<Integer> stack;

public class Main {
    static int n;
    static List<List<Integer>> adj;
    static int[] sccId, discovered;
    static Stack<Integer> stack;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken());

        adj = new ArrayList<>();
        stack = new Stack<>();
        sccId = new int[n+1];
        discovered = new int[n+1];

        for (int i = 0; i <= n; i++) {
            discovered[i] = -1; sccId[i] = -1;
        }

        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj.get(v).add(u);
        }
        sol();
    }

    private static void sol() {
        List<Set<Integer>> groups = new ArrayList<>();
        List<List<Integer>> g_edge = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            groups.add(new HashSet<>());
            g_edge.add(new ArrayList<>());
        }
        for (int i = 1; i <= n; i++) {
            if(discovered[i] == -1) scc(i);
        }
        for (int i = 1; i <= n; i++) {
            groups.get(sccId[i]).add(i);
        }
       
        for (int i = 1; i < adj.size(); i++) {
            for (int j = 0; j < adj.get(i).size(); j++) {
                int child = adj.get(i).get(j);
                if(sccId[i] != sccId[child]) {
                    if(!g_edge.get(sccId[i]).contains(sccId[child]))
                        g_edge.get(sccId[i]).add(sccId[child]);
                }
            }
        }

        int max = 0;
        int[] dp = new int[n+1];
        Arrays.fill(dp,-1);
        for (int i = 1; i < groups.size(); i++) {
            max = Math.max(max,dfsGroup(i,groups, g_edge,dp));
        }
        List<Integer> ret = new ArrayList<>();
        for (int i = 1; i < dp.length; i++) {
            if(max == dp[i]) {
                Iterator<Integer> it = groups.get(i).iterator();
                while(it.hasNext()) {
                    ret.add(it.next());
                }
            }
        }

        Collections.sort(ret);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ret.size(); i++) {
            sb.append(ret.get(i)+" ");
        }

        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb.toString());
    }

    public static int dfsGroup(int here, List<Set<Integer>> groups, List<List<Integer>> g_edge,int[] dp) {
        if(dp[here] != -1) return dp[here];

        int size = groups.get(here).size();
        for (int i = 0; i < g_edge.get(here).size(); i++) {
            int there = g_edge.get(here).get(i);

            size += dfsGroup(there,groups,g_edge,dp);
        }
        dp[here] = size;
        return dp[here];
    }


    
    static int sccCnt =1, vertexCnt = 0;
    public static int scc(int here) {
        discovered[here] = ++vertexCnt;
        int ret = discovered[here];

        stack.push(here);
        for (int i = 0; i < adj.get(here).size(); i++) {
            int there = adj.get(here).get(i);
           
            if(discovered[there] == -1)
                ret = Math.min(ret, scc(there));
           
            else if(sccId[there] == -1)
                ret = Math.min(ret, discovered[there]);
        }

       
        if(ret == discovered[here]) {
            while(!stack.isEmpty()) {
                int t = stack.pop();
                sccId[t] = sccCnt;
                if(t == here) break;
            }
            ++sccCnt;
        }
        return ret;
    }

}

chldntjr1211 5년 전 0

dfs에서 dp방식으로 구할수가 없네요. 그래프간 교차간선 때문에 중간에 값이 중복되서 더해지는 경우가 생기네요.

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

문제

문제

출처

ICPC

반례를 도저히 찾을 수가 없습니다 ㅜㅜ

chldntjr1211 5년 전 0

chldntjr1211 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말