Week 5 | Basics of Graph Theory
24 April, 2021
What was discussed?
This class was on basic stuff of graph theory- the stuff you should go through after learning bfs/dfs/graph representations.
You can find the pdf in this link.
Recording
Unfortunately, zoom recordings were somewhat corrupted, so I couldn't merge them. I uploaded the partial clips in this gdrive folder.
Bonus
-
1470D - Strange Housing: You are given a graph with $N$ nodes and $M$ edges. Color each node in black/white, such that if two nodes are adjacent, then both of them cannot be black, and if you consider only the edges that have black node at one of its endpoint, the graph still remains connected, or say it's impossible. $2 \le N \le 3\cdot 10^5, 0 \le M \le 3\cdot 10^5$.
References