search

Team-Kek / Notebook

Implementations of algorithms that might be useful in ICPC.
1 stars 0 forks source link

Bridges and articulation points #9

Open maxhwardg opened 8 years ago

ZacharyForman commented 8 years ago

Any suggested algos for this?

maxhwardg commented 8 years ago

Anything linear (or n log n) time that you understand. It's pretty much just do a DFS and keep vertex opening times, and then do the obvious things you need to. There are a lot of cases to remember though, so it's worth having in a notebook.

I think the easiest algorithm is to find them both using a minimalist DP / DFS at the same time: https://gist.github.com/maxhwardg/fee88f60c4d9879df8fd18ae6f164d0f

But usually you do a bunch of gross DFSes. There's a million different algorithms for this.