search

dev-onejun / Algorithm-Study

[Since 2019] Algorithm Study
0 stars 1 forks source link

CODEFORCES: 217A - Ice Skating #9

Closed dev-onejun closed 1 year ago

dev-onejun commented 1 year ago

https://codeforces.com/problemset/problem/217/A

dev-onejun commented 1 year ago

using BFS to find the minumum number of snowdrifts to heap up.

(But I wonder .. because this problem uses 2nd-dimension, isn’t it clear that the maximum required snowdrifts is only 2 ?)

dev-onejun commented 1 year ago

Idea

The idea written above is little wrong. It is right to solve the problem using BFS. However, the problem is about Complete Graph. So as BFS, checking the snowdrifts are connected between some two nodes or required to be connected.

dev-onejun commented 1 year ago

Submission

https://codeforces.com/contest/217/submission/193947506

Comment after solving

It was not matter whether BFS or DFS.

Just determine the nodes are connected or not using whatever search algorithms you want. And the number of required nodes(snowdrifts) is same with the number of connected graphs that can be made (actually minus one), because it is on 2nd-dimension.