athos@671: // -*- c++ -*- athos@671: #include athos@671: #include athos@671: athos@671: #include athos@671: //#include alpar@921: #include alpar@921: #include alpar@921: #include athos@671: #include athos@671: alpar@921: using namespace lemon; athos@671: athos@671: int main() { athos@671: typedef SageGraph Graph; athos@671: typedef Graph::Node Node; athos@671: typedef Graph::NodeIt NodeIt; athos@671: typedef Graph::Edge Edge; athos@671: typedef Graph::EdgeIt EdgeIt; athos@671: typedef Graph::OutEdgeIt OutEdgeIt; athos@671: athos@671: Graph g; athos@671: Node s, t; athos@671: Graph::EdgeMap cap(g); athos@671: //readDimacsMaxFlow(std::cin, g, s, t, cap); athos@671: readDimacs(std::cin, g); athos@671: athos@671: Graph::NodeMap pred(g); athos@671: athos@671: Timer ts; athos@671: /* athos@671: { athos@671: ts.reset(); athos@671: Graph::NodeMap reached(g); athos@671: reached.set(s, true); athos@671: pred.set(s, INVALID); athos@671: std::queue bfs_queue; athos@671: bfs_queue.push(t); athos@671: while (!bfs_queue.empty()) { athos@671: Node v=bfs_queue.front(); athos@671: bfs_queue.pop(); athos@671: OutEdgeIt e; athos@671: for(g.first(e,v); g.valid(e); g.next(e)) { athos@671: Node w=g.head(e); athos@671: if (!reached[w]) { athos@671: bfs_queue.push(w); athos@671: reached.set(w, true); athos@671: pred.set(w, e); athos@671: } athos@671: } athos@671: } athos@671: athos@671: std::cout << ts << std::endl; athos@671: } athos@671: */ athos@671: athos@671: { athos@671: ts.reset(); athos@671: Graph::NodeMap bfs_reached(g); athos@671: Graph::NodeMap bfs_pred(g); athos@671: Graph::NodeMap bfs_dist(g); athos@671: athos@671: Bfs< Graph, Graph::NodeMap, athos@671: Graph::NodeMap, Graph::NodeMap > athos@671: bfs(g,bfs_reached, bfs_pred, bfs_dist ); athos@671: bfs.run(s); athos@671: /* athos@671: pred.set(s, INVALID); athos@671: while (!bfs.finished()) { athos@671: ++bfs; athos@671: if (g.valid(bfs) && bfs.isBNodeNewlyReached()) athos@671: pred.set(bfs.bNode(), bfs); athos@671: } athos@671: */ athos@671: std::cout << ts << std::endl; athos@671: } athos@671: athos@671: return 0; athos@671: }