Submission #423600


Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
 
class UnionFindTree{
 
//各ノードの親を保管するリスト。親がもうない場合は-1。
  private int[] ufTree;
 
  public UnionFindTree(int num){
    ufTree = new int[num];
    for(int i = 0; i < num; i++){
      ufTree[i] = -1;
    }
  }
 
  public void doUnion(int a, int b){
    if(a == b){return;}
    int aend = a;
    int bend = b;
    LinkedList<Integer> pasta = new LinkedList<Integer>();
    LinkedList<Integer> pastb = new LinkedList<Integer>();
    pasta.push(aend); pastb.push(bend);    
    while(ufTree[aend] >= 0){
      aend = ufTree[aend];
      pasta.push(aend);
    }
    while(ufTree[bend] >= 0){
      bend = ufTree[bend];
      pastb.push(bend);
    }
    if(aend == bend){
      return;
    }else if(aend > bend){
      while(!pasta.isEmpty()){
        int anode = pasta.pop();
        ufTree[anode] = bend;
      }
    }else{
      while(!pastb.isEmpty()){
        int bnode = pastb.pop();
        ufTree[bnode] = aend;
      }
    }
    //あるノードの親は、自分より小さい番号になる
  }
 
  public boolean askUnion(int a, int b){
    if(a == b){return true;}

    int aend = a;
    LinkedList<Integer> pastnodes = new LinkedList<Integer>();
    while(ufTree[aend] >= 0){
      pastnodes.push(aend);
      aend = ufTree[aend];
    }
    while(!pastnodes.isEmpty()){
      int pastnode = pastnodes.pop();
      ufTree[pastnode] = aend;
    }


    int bend = b;
    while(ufTree[bend] >= 0){
      pastnodes.push(bend);
      bend = ufTree[bend];
    }
    while(!pastnodes.isEmpty()){
      int pastnode = pastnodes.pop();
      ufTree[pastnode] = bend;
    }
    return aend == bend;
  }
}
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
  
    int n = sc.nextInt();
    int qnum = sc.nextInt();
    UnionFindTree u = new UnionFindTree(n);
    for(int qcount = 0; qcount < qnum; qcount++){
      int qnumber = sc.nextInt();
      int a = sc.nextInt();
      int b = sc.nextInt();
      if(qnumber == 0){
        u.doUnion(a, b);  
      }else{
        System.out.println(u.askUnion(a, b) ? "Yes" : "No");
      }
    }
  }
 
//nextChar を追加したよ!
 
//System.out.printf("? %d %d\n", i, j);
 
  
// LinkedList<Integer>[] setsu = new LinkedList[n];
// for(int i = 0; i < n; i++){
//   setsu[i] = new LinkedList<Integer>();
// } 
 
 //ここからテンプレ
  static class InputReader {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
      private SpaceCharFilter filter;
 
      public InputReader(InputStream stream) {
          this.stream = stream;
      }
 
      public int next() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextStr() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        StringBuffer str = new StringBuffer();
        do{
          str.append((char)c);
          c = next();
        }while(!isSpaceChar(c));
        return str.toString();
      }
 
      public char nextChar() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        char ret;
        do{
          ret = (char)c;
          c = next();
        }while(!isSpaceChar(c));
        return ret;
      }
 
      public int nextInt() {
          int c = next();
          while (isSpaceChar(c))
              c = next();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = next();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = next();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public boolean isSpaceChar(int c) {
          if (filter != null)
              return filter.isSpaceChar(c);
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      public interface SpaceCharFilter {
          public boolean isSpaceChar(int ch);
      }
  }
}

Submission Info

Submission Time
Task B - Union Find
User fuzuiR
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 4919 Byte
Status AC
Exec Time 2405 ms
Memory 36096 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 19
Set Name Test Cases
Sample 00_sample_01.txt
All 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 367 ms 22336 KB
subtask_01_01.txt AC 1552 ms 34608 KB
subtask_01_02.txt AC 372 ms 23284 KB
subtask_01_03.txt AC 1939 ms 34916 KB
subtask_01_04.txt AC 1970 ms 35612 KB
subtask_01_05.txt AC 818 ms 28456 KB
subtask_01_06.txt AC 848 ms 29760 KB
subtask_01_07.txt AC 2172 ms 35004 KB
subtask_01_08.txt AC 1939 ms 35632 KB
subtask_01_09.txt AC 374 ms 22276 KB
subtask_01_10.txt AC 391 ms 23408 KB
subtask_01_11.txt AC 2276 ms 35228 KB
subtask_01_12.txt AC 2220 ms 35264 KB
subtask_01_13.txt AC 2030 ms 35348 KB
subtask_01_14.txt AC 394 ms 23700 KB
subtask_01_15.txt AC 1904 ms 35280 KB
subtask_01_16.txt AC 2405 ms 35684 KB
subtask_01_17.txt AC 1666 ms 36084 KB
subtask_01_18.txt AC 1703 ms 36096 KB