Train
National Olympiad — Regional round (2023 season)
Submission name: train.cpp
Problem summary
A connected undirected multigraph has rail lines of type 1 or 2. Construct a closed route starting at station 1 that uses every line at least once and at most its type number of times, or report impossibility.
Input
N M, then M triples u v t; line IDs are 1,…,M in input order.
Output
−1 if impossible; otherwise route length S and a sequence of S line IDs. Any valid route is accepted.
Constraints
2 ≤ N ≤ 100000; 1 ≤ M ≤ 1000000; 1 ≤ u,v ≤ N; u≠v; t∈{1,2}; parallel lines allowed; graph connected.
Worked example
Independent two-station example; either ordering of the two line IDs is valid.
Input
2 2 1 2 1 1 2 1
Output
2 1 2
Solution analysis
- Begin with one copy of every line. A closed route exists precisely when every vertex has even degree. We may duplicate some type-2 lines, and each duplication flips the parity at its two endpoints. Build a spanning forest of the graph consisting only of type-2 lines.
- Process each forest from leaves to root. If a nonroot vertex currently has odd parity, duplicate its parent edge; this fixes its parity and flips its parent. If it is even, do not duplicate that edge. At the root, odd parity means impossibility: no type-2 edge crosses that optional-edge component, and internal duplications cannot change its total parity. If the root is even, all vertices of the component are now even.
- The resulting connected multigraph has one or two copies of each allowed edge and all degrees even. Use iterative Hierholzer traversal from station 1, treating duplicated copies as separate uses but printing the original line IDs. In the independent example, the two parallel required lines form a length-two closed route.
Why it works
Every valid route determines an even-degree multigraph by its traversal counts. Inside a type-2 component, duplicating an edge flips two parities, so an odd total initial parity is an invariant obstruction. The leaf procedure fixes each nonroot vertex without affecting any already processed descendant; its root is even exactly when the component total is even. Thus it constructs valid multiplicities whenever the necessary condition holds. Connectivity is preserved because every original edge remains. Euler’s theorem then guarantees a closed route, and Hierholzer outputs one using exactly those multiplicities.
Watch out. Keep parallel edges distinct by ID. Duplicate only type-2 edges and output edge IDs rather than vertices.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every valid route determines an even-degree multigraph by its traversal counts. Inside a
// type-2 component, duplicating an edge flips two parities, so an odd total initial parity is an
// invariant obstruction.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<utility>
#include<vector>
using namespace std;
struct DSU{
vector<int>parent,size;
explicit DSU(int n):parent(n),size(n,1){
iota(parent.begin(),parent.end(),0);
}
int find(int x){
while(parent[x]!=x){
parent[x]=parent[parent[x]];
x=parent[x];
}
return x;
}
bool join(int a,int b){
a=find(a);
b=find(b);
if(a==b){
return false;
}
if(size[a]<size[b]){
swap(a,b);
}
parent[b]=a;
size[a]+=size[b];
return true;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<int>from(m),to(m),copies(m,1),parity(n);
vector<vector<int>>graph(n),forest(n);
DSU dsu(n);
for(int id=0;id<m;++id){
int type;
cin>>from[id]>>to[id]>>type;
--from[id];
--to[id];
graph[from[id]].push_back(id);
graph[to[id]].push_back(id);
parity[from[id]]^=1;
parity[to[id]]^=1;
if(type==2&&dsu.join(from[id],to[id])){
forest[from[id]].push_back(id);
forest[to[id]].push_back(id);
}
}
vector<int>parent(n,-1),parentEdge(n,-1),order;
for(int root=0;root<n;++root){
if(parent[root]!=-1){
continue;
}
parent[root]=root;
size_t begin=order.size();
order.push_back(root);
for(size_t i=begin;i<order.size();++i){
int v=order[i];
for(int id:forest[v]){
int u=from[id]^to[id]^v;
if(parent[u]==-1){
parent[u]=v;
parentEdge[u]=id;
order.push_back(u);
}
}
}
}
for(int i=n-1;i>=0;--i){
int v=order[i];
if(parent[v]==v){
if(parity[v]){
cout<<-1<<'\n';
return 0;
}
}
else if(parity[v]){
++copies[parentEdge[v]];
parity[v]=0;
parity[parent[v]]^=1;
}
}
vector<size_t>cursor(n);
vector<pair<int,int>>stack;
vector<int>route;
stack.push_back({0,-1});
while(!stack.empty()){
int v=stack.back().first;
while(cursor[v]<graph[v].size()&&copies[graph[v][cursor[v]]]==0){
++cursor[v];
}
if(cursor[v]==graph[v].size()){
int incoming=stack.back().second;
stack.pop_back();
if(incoming!=-1){
route.push_back(incoming+1);
}
}
else{
int id=graph[v][cursor[v]];
--copies[id];
stack.push_back({from[id]^to[id]^v,id});
}
}
reverse(route.begin(),route.end());
cout<<route.size()<<'\n';
for(size_t i=0;i<route.size();++i){
cout<<(i?" ":"")<<route[i];
}
cout<<'\n';
}