소프트웨어 익스퍼트 1248 (software expert 1248)

Algorithms / software expert 10 Nov 2019
Software expert academy Software expert 1248 소프트웨어 익스퍼트 아카데미 소프트웨어 익스퍼트 1248

소프트웨어 익스퍼트 1248 (software expert 1248)

소프트웨어 익스퍼트 1248

Software Expert Academy 1248

소프트웨어 익스퍼트 아카데미 1248 (Software Expert Academy 1248)

https://swexpertacademy.com

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class SWE1248 {
    static int t, T, V, E, n1, n2, u, v;
    static String ins[];
    static Node[] g = new Node[10001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        t = T = Integer.parseInt(br.readLine());
        while (T-- != 0) {
            ins = br.readLine().split(" ");
            V = Integer.parseInt(ins[0]);E = Integer.parseInt(ins[1]);
            n1 = Integer.parseInt(ins[2]);n2 = Integer.parseInt(ins[3]);
            ins = br.readLine().split(" ");
            for (int i = 1; i <= V; i++) g[i] = new Node();
            for (int i = 0; i < 2 * E; i += 2) {
                u = Integer.parseInt(ins[i]);
                v = Integer.parseInt(ins[i + 1]);
                if (g[u].lc == -1) g[u].lc = v;
                else g[u].rc = v;
                g[v].p = u;
            }
            ArrayList<Integer> path1 = bfs(n1);
            ArrayList<Integer> path2 = bfs(n2);
            int commonParent = -1;
            boolean isCommonParent = false;
            for (int i = 0; i < path1.size(); i++) {
                for (int j = 0; j < path2.size(); j++) {
                    if (path1.get(i).equals(path2.get(j))) {
                        isCommonParent = true;
                        commonParent = path1.get(i);
                        break;
                    }
                }
                if (isCommonParent) break;
            }
            bw.write("#" + (t - T) + " " + commonParent + " " + bfs2(commonParent) + "\n");
            bw.flush();
        }
        bw.close();
    }

    public static ArrayList<Integer> bfs(int s) {
        Queue<Integer> q = new LinkedList<>();
        ArrayList<Integer> l = new ArrayList<>();
        l.add(s);q.add(s);
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (g[cur].p != -1) {
                q.offer(g[cur].p);
                l.add(g[cur].p);
            } else break;
        }
        return l;
    }

    public static int bfs2(int s) {
        Queue<Integer> q = new LinkedList<>();
        ArrayList<Integer> l = new ArrayList<>();
        l.add(s);q.add(s);
        int count = 0;
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (g[cur].rc != -1) q.offer(g[cur].rc);
            if (g[cur].lc != -1) q.offer(g[cur].lc);
            count++;
        }
        return count;
    }

    private static class Node {
        int p, lc, rc;
        Node () { p = lc = rc = -1; }

    }

}

설명