AtCoderBeginnerContest231 D問題400点 「Neighbors」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 10^5
$ M \leq 10^5
気持ち
$ A_i, B_iが隣り合うというのは、グラフ理論で考えると辺をつなぐという操作に相当します。 よって、人をノードとして考えて、条件=辺として捉えると、以下の解法のように2条件に落とし込めるなとなります。
ものごとをグラフ理論で捉えるとわかりやすいというのは競技プログラミングだとよくあります。
解法
色々と書いてみると以下のような状態の場合、うまく作れないことが分かります。
ある$ iさんが隣り合わなければならない人が 3 人以上いる
条件を辺として結ぶと閉路ができてしまう
https://gyazo.com/96ac71b3cefaf6d7d65293825e441994
https://gyazo.com/1b83aaab7ec812bc319f2aaeb34cae4c
よって、以上の条件2つを判定すればいいです。
難しいのは下の条件です。
閉路の判定などは UnionFind や BFS / DFS などを利用できます。
UnionFind のほうが楽なので、もし UnionFind を持っているのであればそちらで実装すると良さそうです。
計算量
$ O(N+M)
新たな学び
Go のコンストラクタでは、*T を返り値とし、NewT のような名前をつける
NewT 関数のなかでメモリ領域にオブジェクトを確保する (&T や new(T))
確保したオブジェクトのポインタを返す
関数は基本的に大文字で実装する
変数は小文字っぽい?(キャメル)
反省点
コード
code: go
type UnionFind struct {
par []int
sizes []int
}
func NewUnionFind(n int) *UnionFind {
ret := &UnionFind{
par: make([]int, n),
sizes: make([]int, n),
}
for i := 0; i < n; i++ {
}
return ret
}
func (uf *UnionFind) Find(x int) int {
return x
} else {
return ret
}
}
func (uf *UnionFind) Unite(x, y int) bool {
x = uf.Find(x)
y = uf.Find(y)
if x == y {
return false
}
if uf.sizesx < uf.sizesy { x, y = y, x
}
return true
}
func (uf *UnionFind) Same(x, y int) bool {
return uf.Find(x) == uf.Find(y)
}
func (uf *UnionFind) GetSize(x int) int {
}
func main() {
io := NewIo()
defer io.Flush()
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
N, M := io.NextInt(), io.NextInt()
A, B := make([]int, M), make([]int, M)
in := make([]int, N)
for i := 0; i < M; i++ {
Ai, Bi = io.NextInt(), io.NextInt() }
for i := 0; i < N; i++ {
io.PrintLn("No")
return
}
}
UF := NewUnionFind(N)
for i := 0; i < M; i++ {
fmt.Println("No")
return
}
}
fmt.Println("Yes")
}