結果

問題 No.556 仁義なきサルたち
ユーザー watarimaycry2
提出日時 2020-03-05 19:31:23
言語 JavaScript
(node v23.5.0)
結果
AC  
実行時間 127 ms / 2,000 ms
コード長 3,996 bytes
コンパイル時間 28 ms
コンパイル使用メモリ 6,692 KB
実行使用メモリ 47,704 KB
最終ジャッジ日時 2024-10-13 01:31:56
合計ジャッジ時間 2,807 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

var input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
var obj = {
  "list" : input,
  "index" : 0,
  "max" : input.length,
  "next" : function(){
    if(!this.hasNext()){throw "NoSuchElementException:次に要素は無いよ";}
    var returnObj = this.list[this.index];
    this.index++;
    return returnObj;
  },
  "hasNext" : function(){return (this.index < this.max);}
}
function next(){return obj.next();}
function nextInt(){return myconv(next(),1);}
function nextStrArray(){return myconv(next(),2);}//半角スペース分割
function nextIntArray(){return myconv(next(),4);}//半角スペース + 数値化
function nextCharArray(){return myconv(next(),6);}//1文字分割
function hasNext(){return obj.hasNext();}
function myout(t){console.log(t);}//標準出力
function myerr(t){console.error(t);}//標準エラー出力
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す　1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map((a)=>Number(a));case 6:return i.split("");case 7:return i.split("").map((a)=>Number(a));case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}
var unionFind = {
  "list" : null,
  //全てのインデックスは「-X(親、絶対値はグループの大きさ)」「自分が属する親(≒根)」のいずれかを持つ。
  //最初はみんなグループの大きさ1の親
  "init" : function(n){
    this.list = new Array(n).fill(-1);
  },
  //同じ親を持つか
  "isSame" : function(mae, ato){
    return this.getRootIndex(mae) == this.getRootIndex(ato);
  },
  //自身の親インデックスをたどって根っこに着く
  //親にたどり終えたら子に帰っていくついでに、子たちに「共通の親を持っている」ことを知らせる
  "getRootIndex" : function(index){
    if(this.list[index] < 0){
       return index;
    }else{
       this.list[index] = this.getRootIndex(this.list[index]);
      return this.list[index];
    }
  },
  //異なる親同士のまとまりを一つにする（同じ親ならスルー）
  //小さいグループの親が大きいグループの親の直下に着く
  //グループの大きさも更新する
  "doUnion" : function(mae, ato){
    var maeRoot = this.getRootIndex(mae);
    var atoRoot = this.getRootIndex(ato);
    if(!this.isSame(maeRoot, atoRoot)){
       if(this.getSize(maeRoot) > this.getSize(atoRoot)){
          this.list[maeRoot] += this.list[atoRoot];
         this.list[atoRoot] = maeRoot;
       }else if(this.getSize(maeRoot) < this.getSize(atoRoot)){
          this.list[atoRoot] += this.list[maeRoot];
         this.list[maeRoot] = atoRoot;      
       }else{
         if(maeRoot < atoRoot){
            this.list[maeRoot] += this.list[atoRoot];
            this.list[atoRoot] = maeRoot;
         }else{
            this.list[atoRoot] += this.list[maeRoot];
            this.list[maeRoot] = atoRoot;      
         }
       }
    }
  },
  //「-X(親、絶対値はグループの大きさ)」
  //なので、インデックスを指定→親を知る→親の持つグループの大きさがわかる。
  //ただしマイナス値なので、-1を掛け算して返す。
  "getSize" : function(index){
    return -this.list[this.getRootIndex(index)];
  }
}
Main();
function Main(){
  var one = nextIntArray();
  var N = one[0];
  var M = one[1];
  unionFind.init(N);
  for(var i = 0; i < M; i++){
    var tmp = nextIntArray();
    unionFind.doUnion(tmp[0] - 1, tmp[1] - 1);
  }
  myerr(unionFind.list);
  var output = new Array(N);
  for(var i = 0; i < N; i++){
    output[i] = unionFind.getRootIndex(i) + 1;
  }
  myout(myconv(output,9));
}
0