結果

問題 No.1390 Get together
コンテスト
ユーザー masashi0217
提出日時 2021-03-26 01:50:16
言語 Ruby
(3.4.1)
結果
RE  
実行時間 -
コード長 3,190 bytes
コンパイル時間 99 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 30,592 KB
最終ジャッジ日時 2024-11-27 11:25:26
合計ジャッジ時間 12,247 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 RE * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class Un
    def initialize(n)
        @size = Array.new(n,1)
        @mae = Array.new(n,-1)
        @rank = Array.new(n,0)
    end
    def find(n)
        ans = 0
        if @mae[n] == -1
             return n
        else
            ans = find(@mae[n])
            return ans
        end
    end
    def same(x,y)
        point = 0
        if @mae[x] == -1 && @mae[y] == -1
            point_1 = find(y)
            point_2 = find(x)
            if point_1 == point_2
                ok = true
                return ok
            end
        elsif @mae[x] == -1
            point = find(y)
            if point == x
                ok = true
                return ok
            end
        elsif @mae[y] == -1
            point = find(x)
            if point == y
                ok = true
                return ok
            end
        else
            point_1 = find(x)
            point_2 = find(y)
            if point_1 == point_2
                ok = true
                return ok
            end
        end
    end
    def union(x,y)
        point = 0
        if @mae[x] == -1 && @mae[y] == -1
            point_1 = find(x)
            point_2 = find(y)
            if @rank[point_1] < @rank[point_2]
                @size[point_2] += @size[point_1]
                @mae[point_1] = point_2 
            else
                # print "point_1" + " " + "#{point_1}" + "\n"
                # print "point_2" + " " + "#{point_2}" + "\n"
                @size[point_1] += @size[point_2]
                @mae[point_2] = point_1
                @rank[point_1] += 1 if @rank[point_1] == @rank[point_2]
            end
        elsif @mae[x] == -1
            point = find(y)
            if @rank[point] < @rank[x]
                @size[x] += @size[point]
                @mae[point] = x
            else
                @size[point] += @size[x]
                @mae[x] = point
                @rank[ponit] += 1 if @rank[point] == @rank[x]
            end
        elsif @mae[y] == -1
            point = find(x)
            if @rank[point] < @rank[y]
                @size[y] += @size[point]
                @mae[point] = y
            else
                @size[point] += @size[y]
                @mae[y] = point
                @rank[point] += 1 if @rank[point] == @rank[y]
            end
        else
            point_1 = find(x)
            point_2 = find(y)
            if @rank[point_1] < @rank[point_2]
                @size[point_2] += @size[point_1]
                @mae[point_1] = point_2 
            else
                @size[point_1] += @size[point_2]
                @mae[point_2] = point_1
                @rank[ponit_1] += 1 if @rank[point_1] == @rank[point_2]
            end
        end
        # p @rank
        # p @size
        # p @mae
    end
end

hash = Hash.new{|i,j| hash[j] = []}
n, m = gets.chomp.split(" ").map(&:to_i)
n.times do
    b, c = gets.chomp.split(" ").map(&:to_i)
    hash[c] << b
end
uf = Un.new(m)
count = 0
hash.each do |box,colors|
    # puts "-----"
    # p colors
    # puts "~~~~~~"
    colors.each_cons(2) do |i,j|
        tf = uf.same(i-1,j-1)
        next if tf
        count += 1
        uf.union(i-1,j-1)
    end
end
puts count
0