Hi,

We had a problem-solving session on graph algorithms today. I selected problems that don’t require many prerequisites and are focused on generating ideas. I hope you find it enjoyable and educational.

This video is for people from starter to expert level.

330B — Road Construction

In this problem, we use a constraint on m that helps us solve it easily.

The link to the problem: https://mirror.codeforces.com/problemset/problem/330/B

687A — NP-Hard Problem

In this problem, you’ll get familiar with the concept of a vertex cover, and we’ll apply what we’ve learned about bipartite graphs.

The link to the problem: https://mirror.codeforces.com/problemset/problem/687/A

1093D — Beautiful Graph

The idea of the previous problem helps a lot to solve this one as well.

The link to the problem: https://mirror.codeforces.com/problemset/problem/1093/D

369C — Valera and Elections

In here, we use a trick that is useful in many tree problems.

The link to the problem: https://mirror.codeforces.com/problemset/problem/369/C

429A — Xor-tree

Here, we see how to pass the state in DFS and use logical arguments and facts to solve the problem.

The link to the problem: https://mirror.codeforces.com/problemset/problem/429/A

105053E — Expanding STACKS

This is a problem we came across recently while practicing for ICPC. We’ll see how graph algorithms can be used to solve a problem that doesn’t initially seem like a graph problem.

The link to the problem: https://mirror.codeforces.com/gym/105053/problem/E

I hope this stream and the consequent ones will be helpful.