marci@358: // -*- c++ -*- marci@358: #include marci@358: #include marci@358: marci@642: #include marci@389: //#include marci@555: #include marci@555: #include marci@640: #include marci@602: #include marci@358: marci@358: using namespace hugo; marci@358: marci@358: int main() { marci@642: typedef SageGraph Graph; marci@358: typedef Graph::Node Node; marci@358: typedef Graph::NodeIt NodeIt; marci@358: typedef Graph::Edge Edge; marci@358: typedef Graph::EdgeIt EdgeIt; marci@358: typedef Graph::OutEdgeIt OutEdgeIt; marci@358: marci@577: Graph g; marci@358: Node s, t; marci@577: Graph::EdgeMap cap(g); marci@577: //readDimacsMaxFlow(std::cin, g, s, t, cap); marci@577: readDimacs(std::cin, g); marci@577: marci@577: Graph::NodeMap pred(g); marci@358: Timer ts; marci@358: { marci@358: ts.reset(); marci@577: Graph::NodeMap reached(g); marci@358: reached.set(s, true); marci@358: pred.set(s, INVALID); marci@358: std::queue bfs_queue; marci@358: bfs_queue.push(t); marci@358: while (!bfs_queue.empty()) { marci@358: Node v=bfs_queue.front(); marci@358: bfs_queue.pop(); marci@358: OutEdgeIt e; marci@577: for(g.first(e,v); g.valid(e); g.next(e)) { marci@577: Node w=g.head(e); marci@358: if (!reached[w]) { marci@358: bfs_queue.push(w); marci@358: reached.set(w, true); marci@358: pred.set(w, e); marci@358: } marci@358: } marci@358: } marci@358: marci@358: std::cout << ts << std::endl; marci@358: } marci@358: marci@358: { marci@358: ts.reset(); marci@577: BfsIterator< Graph, Graph::NodeMap > bfs(g); marci@358: bfs.pushAndSetReached(s); marci@358: pred.set(s, INVALID); marci@358: while (!bfs.finished()) { marci@358: ++bfs; marci@577: if (g.valid(bfs) && bfs.isBNodeNewlyReached()) marci@358: pred.set(bfs.bNode(), bfs); marci@358: } marci@358: std::cout << ts << std::endl; marci@358: } marci@358: marci@358: return 0; marci@358: }