[CF 453C] Little Pony and Summer Sun Celebration

作法：

首先如果有兩個連通塊裡都有$1$那顯然無解，因此現在只要考慮有一個連通塊有$1$的情形。通常這種構造題只要隨便取個生成樹DFS下去就可以了。考慮在DFS的過程中，當DFS完$x$這個點時$x$必須要完成他的目標，然後回到他父親（記為$f$）。如果發現$x$還需要被走一次，那麼就走$f\rightarrow x\rightarrow f$就可以讓$x$多走一次了，而如果$x$不用再被走一次就直接回去$f$。這樣可以處理根節點以外的所有點，至於如果回到根節點時還沒滿足條件，那麼隨便取他的一個孩子$s$，走$s\rightarrow x\rightarrow s$就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
vector<int> v[maxn],ans ;
bool vis[maxn] ;
int c[maxn] ;
inline void go(int x){ans.push_back(x) ; c[x]^=1 ;}
void dfs(int x)
{
    vis[x]=1 ;
    for(auto i : v[x]) if(!vis[i])
    {
        go(i) ; dfs(i) ; go(x) ;
        if(c[i]) go(i) , go(x) ;
    }
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    for(int i=1;i<=n;i++) scanf("%d",&c[i]) ;
    for(int i=1;i<=n;i++) if(c[i])
    {
        go(i) ; dfs(i) ;
        if(c[i]) go(v[i][0]) , go(i) , go(v[i][0]) ;
        break ;
    }
    for(int i=1;i<=n;i++) if(c[i])
        {printf("-1\n") ; return 0 ;}
    printf("%d\n",ans.size()) ;
    for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i+1==ans.size()?'\n':' ') ;
}