D - Collision

二部グラフの問題

実際に役に立った記事

前編

DFSの導入部分なので見ておいて損はない．

後編

実践編　前編を理解してからのほうが理解しやすいと思う．

code:swift

func main() {

let input = readLine()!.split(separator: " ").map { Int($0)! }

let (V,Q) = (input0,input1)

var color = Int.init(repeating: -1, count: V+1)

var graph = Int.init(repeating: [], count: V+1)

func dfs(graph: Int, v: Int, seen: Int = 0) -> Bool {

colorv = seen

for ver in graphv {

if colorver != -1 {

if (colorver == seen) { return false }

continue

}

if !dfs(graph: graph, v: ver, seen: 1 - seen) { return false }

}

return true

}

(0..<V-1).forEach { _ in

let AB = readLine()!.split(separator: " ").map { Int($0)! }

let (A, B) = (AB0, AB1)

graphA.append(B)

graphB.append(A)

}

//完全二部グラフになっているか確認するコード

//print(dfs(graph: graph, v: 1) ? "Yes":"No")

_ = dfs(graph: graph, v: 1)

(0..<Q).forEach { _ in

let CD = readLine()!.split(separator: " ").map { Int($0)! }

let (C, D) = (CD0, CD1)

if colorC == colorD {

print("Town")

} else {

print("Road")

}

main()