Submission #17562463

---

Source Code Expand

struct UnionFind {
    var par:[Int]
    var rank:[Int]
    var n:Int
    //最初は全てが根であるとして初期化
    init(n:Int){
        self.n = n
        self.par = Array(repeating:0,count:n)
        self.rank = Array(repeating:0,count:n)
        for i in 0..<n{
            par[i] = i
        }
    }
    // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    mutating func root(x:Int) -> Int {
        if par[x] == x{
            return x
        }
        else{
            return root(x:par[x])
        }
    }
    // xとyの木を併合
    mutating func unite (x:Int,y:Int){
        let x = root(x:x)
        let y = root(x:y)
        if x == y{
            return
        }
        if rank[x] < rank[y]{
            par[x] = y
        } else {
            par[y] = x
            if rank[x] == rank[y]{
                rank[x] += 1
            }
        }
    }
    // 2つのデータx, yが属する木が同じならtrueを返す
    mutating func same(x:Int,y:Int)->Bool{
        return root(x:x) == root(x:y)
    }
}

// 標準入力の受け取り
let input = readLine()!.split(separator:" ").map{Int($0)!}
let n = input[0]
let m = input[1]

// UnionFindの初期化
var check = UnionFind(n:n)

// 連結させる
for _ in 0..<m{
    let ab = readLine()!.split(separator:" ").map{Int($0)!}
    let a = ab[0]-1
    let b = ab[1]-1
    check.unite(x:a,y:b)
}

// 根の数をカウント (答えは (根の数) - 1)
var ans = -1
for i in 0..<n{
    if i == check.root(x:i){
        ans += 1
    }
}

// 答えの出力
print(ans)

Submission Info

Judge Result