CODEFORCES: 277A - Learning Languages

dev-onejun / Algorithm-Study

[Since 2019] Algorithm Study

0 stars 1 forks source link

CODEFORCES: 277A - Learning Languages #10

Closed dev-onejun closed 1 year ago

dev-onejun commented 1 year ago

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

dev-onejun commented 1 year ago

Idea

bfs (node: employee, tree: connected if the employees have the same language)
The number of the constructed tree is the answer

dev-onejun commented 1 year ago

Wrong answer on test 4

dev-onejun commented 1 year ago

According to the contest material, The test 4 is a corner case which requires to think all employees do not know any kinds of languages.

Before that, the number of edges which make the constructed graph connected was the only answer of the problem. However, the corner case should be handled separately. If no one had the languages to do, all employees(node) should learn. In other words, the number of nodes becomes the answer.

dev-onejun commented 1 year ago

Submission

https://codeforces.com/contest/277/my