D - Collision
https://atcoder.jp/contests/abc209/tasks/abc209_d
二部グラフの問題
実際に役に立った記事
前編
DFSの導入部分なので見ておいて損はない.
https://qiita.com/drken/items/4a7869c5e304883f539b
後編
実践編 前編を理解してからのほうが理解しやすいと思う.
https://qiita.com/drken/items/a803d4fc4a727e02f7ba#4-グラフ上の様々な例題
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()