UVa Online Judge 一個大水題，先對火做BFS預處理每個格子發生火的最早時間，然後再搞人的就行了。注意會需要用到 ( t, x, y ) 三個變數一組的某種結構，以前都搞什麼雙重pair 真是太恐怖了，tuple我現在還不太會用。。寫完這題就想，我以後就像這樣子做吧。…

I have finally started to understand the LCA algorithm for transforming to RMQ. Here are the basic steps for static LCA queries: 1. DFS from any node as the root for the tree, making timestamps as it goes ( called the Euler's tour ). 3 bas…

1236 -- Network of Schools Given a network, answer at least how many nodes we need to spread information to let the whole graph know, and the minimum directed edges required to add so the whole graph becomes an SCC. The first query is just…

When a directed graph set S satisfies "for every vertex u and v, exists a path from u to v", this graph could be called an SCC. SCC can be found by applying DFS twice. This is called Kosaraju's algorithm O( V + E ). DFS1 will start from an…

A vertex biconnected component (bcc) can be defined as a connected component (cc) that is still a cc after any vertex is plucked out of the graph, and usually we would think about the bcc as the largest component that satisfies. An edge bc…