We continue to use email for information exchange.  And we will use github to post  session notes:

https://github.com/vzhang2008/competitive


Comments

Post a Comment

Popular posts from this blog

Summary of Class 12: Eulerian graph / Eulerian path (USACO 3.3)

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1736 laid the foundations of graph theory and prefigured the idea of topology. Eulerian Cycle ( Eulerian circuit, closed eulerian trail/path ) Eulerian trail (or Eulerian path) is a trail in a finite graph which visits every edge exactly once.  An Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex. A eulerian cycle exists on an undirected graph if and only if the graph is connected  and every vertex has an even degree. A eulerian cycle exists on a directed graph if and only if the graph is connected  and the in-degree of every vertex is equal to its out-degree. (Chinese postman problem) Eulerian Path An undirected graph has Eulerian Path if following two conditions are true. a) the graph is connected b) If zero or two vertices have odd degree and all other vertices have...
Read more

Summary of Class 15 DAG -- Topological Sorting (USACO 4.4)

“To improve is to change; to be perfect is to change often.”  ―  Winston S. Churchill Version Control (or Revision control or source control): Version Control System (VCS) Concurrent Version System (CVS) Subversion (SVN) git command:     git add . (or file)     git commit -m "msg"     git push origin <branch-name> https://services.github.com/on-demand/downloads/github-git-cheat-sheet/ Review of SCC, DFS, BFS SCC: A digraph is strongly connected if every two vertices are  mutually reachable . A strong component of a digraph G is a maximal strongly connected subdigraph of G. Equivalently, a strong component is a subdigraph induced on a maximal set of mutually reachable vertices. Graph DFS: stack-based :  (for loop with visited vertices)     tree edge,     forward edge    ...
Read more

Summary of Class 14 Strongly Connected Components (SCC)

Try not to become a man of success, but rather try to become a man of value.   - Albert Einstein 不自见故明；不自是故彰；不自伐故有功；不自矜 故长。 夫唯不争，故天下莫能与之争。 Data Structure Review (C++ STL) : array(array), dynamic array (vector) doubly linked list (list), singly linked list (forward_list) stack, queue, priority_queue (heap structure) binary tree, binary search tree (BST) graph (adjacent list, adjacent matrix, edge list) union-find data structure  A directed graph is strongly connected if there is a path between all pairs of vertices. https://en.wikipedia.org/wiki/Strongly_connected_component Kosaraju’s algorithm 1) Do DFS and push the vertex to stack S.      For each vertex u of the graph, mark u as unvisited in visited[] array. Let Stack S be empty.      For each vertex u of the graph do dfs(u, visited, S), where dfs() is the recursive subroutine:          mark u as visited:   ...
Read more