Codeforces 453C - Little Pony and Summer Sun Celebration

Problem Statement:
453C - Little Pony and Summer Sun Celebration

Solution:
(How did they come up with such a cute name for a problem statement, I wonder)
A pretty interesting graph problem, which is more of a test on structure construction. The official editorial to this problem is already perfectly clear, I'm writing this purely for my future references.

To solve the problem the brute force way, one can choose any node as a root, and run a DFS on this root, in the following manner: From root, visit the next available odd-parity node, and come back. This works because every nodes in between the path between root and the odd-parity node will be visited twice as the person go forth and back to root. Hence each time we will be eliminating one odd-parity node from consideration, which is nice. Finally, we check how many times we visited root, and if the parity does not match, we simply remove a root node on the tail of the path (i.e., the person did not come back to the root eventually). However, this approach does not guarantee the final path to be within 4n limit.



We extend the above idea to come up with a path that is guaranteed to be \( \leq 4n\) in length by maintaining the following invariance while constructing the path:
By the time we leave a node u, every node belonging to the subtree rooted at u in the DFS tree will have all already consistent in their parity. We also know how many times u is visited during that process of visiting the children of u. From here, we check whether the parity of u matches. If it matches, we simply leave u. Otherwise, we leave u, come back to u, and leave it again, so now the parity will definitely match!

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
int N,M;
vector<vector<int> > adj;
int par[100005];
int vis[100005];
int ctr;
int root_count;
int root;
vector<int> st;
vector<int> tmp;
void dfs(int u){
    vis[u] = 1;
    ++ctr;
    bool isleaf = true;
    int parity = 1;
    st.push_back(u);
    for(int i=0;i<adj[u].size();++i){
        int v = adj[u][i];
        if(vis[v])continue;
        isleaf = false;
        dfs(v);
        st.push_back(u);
        ++parity;
        if(!tmp.empty()){
            st.push_back(tmp.back());
            tmp.pop_back();
            st.push_back(u);
            ++parity;
        }
    }
    if(u==root)root_count = parity;
    if(par[u]!=(parity%2))tmp.push_back(u);
}


int main(){
    int u,v;
    scanf("%d%d",&N,&M);
    adj = vector<vector<int> > (N+3);
    for(int i=0;i<M;++i){
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=N;++i){
        scanf("%d",&par[i]);
    }
    for(int i=1;i<=N;++i){
        if(par[i]==1){
            root = i;
            dfs(i);
            break;
        }
    }
    bool ok = true;
    for(int i=1;i<=N;++i){
        if(!vis[i]&&par[i])ok=false;
        if(!ok)break;
    }   
    if(ok){
        if((root_count%2)!=par[root]){
            if(!st.empty())st.pop_back();
            else st.push_back(root);
        }
        printf("%d\n",(int)st.size());
        for(int i=0;i<st.size();++i){
            if(i!=0)printf(" ");
            printf("%d",st[i]);
        }
        if(st.size()!=0)printf("\n");
    } else {
        printf("-1\n");
    }
    return 0;
}