1717-집합의 표현 (오답)

1. M(연산의 수)이 10만개이므로 2중 for문을 사용하여 리스트를 합쳐주는것은 O(N^2)시간이 걸린다.

2. 집합의 수가 1~100만개지 집합 수의 범위가 1~100만이 아니기때문에 0도 포함되어야한다

(0을 포함안시키고 수행) 

시간복잡도를 다시한번 생각해보고 다른 방법을 찾아봐야겠다

 

import java.util.*;

public class B1717 {
    static int N,M,p,a,b;
    static ArrayList<ArrayList<Integer>> Board;

    public static void main(String[] args) {

        Scanner sc= new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        Board = new ArrayList<>();

        for(int i=1; i<=N; i++){
            ArrayList<Integer> list = new ArrayList<>();
            list.add(i);
            Board.add(list);
        }
        for(int i=0; i<M; i++){

            p = sc.nextInt();
            a = sc.nextInt();
            b = sc.nextInt();
            calc(p,a,b);
            /*
            System.out.println("====");
            for(ArrayList<Integer> j : Board){
                System.out.println(j);
            }
            System.out.println("====");
             */
        }
    }

    private static void calc(int p, int a, int b) {
        boolean isMatch = false;
        if(p == 0){
            ArrayList<Integer> A = new ArrayList<>();
            ArrayList<Integer> B = new ArrayList<>();
            int indexA = 0;
            int indexB = 0;
            for(int i = 0; i<Board.size(); i++){
                for(int j : Board.get(i)){
                    if(j==a){
                        A =Board.get(i);
                        indexA = i;
                    }
                    if(j==b){
                        B =Board.get(i);
                        indexB = i;
                    }
                }
            }
            Board.remove(A);
            if (indexA != indexB) {
                Board.remove(B);
                A.addAll(B);
            }
            Board.add(A);
        }
        else if(p==1){
            for(ArrayList<Integer> board : Board){
                for(int i : board){
                    if(i==a){
                        for(int j : board){
                            if (j == b) {
                                isMatch = true;
                                break;
                            }
                        }
                    }
                }
            }
            if(isMatch) System.out.println("YES");
            if(!isMatch) System.out.println("NO");
        }
    }
}