ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1441. From the History of Gringotts Bank

Eler circuit
Posted by svr 7 Dec 2006 18:17
How do this faster?
1) Adding virtual edges to pairs of vertices with odd degree
2) Building Eler circuit in new graph.
3) Cutting circuit by virtual edges.
But Graph is undirected and when we removing edges
in classic stac algorithm we should use set-class as
dynamic Adj list for each vertex instead of vector-class
Re: Eler circuit
Posted by Denis Koshman 13 Aug 2008 04:55
How to do it even faster: add virtual edges between new virtual point and odd-degree nodes. Just O(N) overhead.
(AC in 0.046 sec)

Edited by author 13.08.2008 05:28
Re: Eler circuit
Posted by Denis Koshman 13 Aug 2008 05:05
As for bidirectionality - just add edges twice and maintain bidirectional indexation between them. Or add all edges to base-0 arraay in the order (v1;v2), (v2;v1), (v3;v4), (v4;v3), etc... then "x XOR 1" will be index of backwards edge.