题意

题目链接

有若干个点和若干条边，每条边都为 $0$ 或 $1$ ，每次可以对一个点进行操作，与这个点相连的所有边的值都会改变（ $0$ 变为 $1$，$1$ 变为 $0$），现在寻求一种方案，使得所有边最终都变为 $1$ ，若找不到这种方案，输出 Impossible 。

解析

首先我们发现，每个点一定是只操作 $1$ 次或 $0$ 次的，因为我们如果对一个点操作 $2$ 次，则这两次操作会相互抵消，是无意义的。

接着我们发现，初值为 $0$ 的边，与之相连的点一定有且只有一个被操作过；初值为 $1$ 的边，与之相连的边一定均未被操作过或均被操作过。也就是说，与 $0$ 相连的点的操作状态是不同的，与 $1$ 相连的点的操作状态是相同的，因此我们考虑染色。

对于一条 $0$ 的边，我们将两个相邻点染成不同颜色，对于一条 $1$ 的边，我们将两个相邻点染成相同颜色，若发现染色矛盾，则输出 Impossible。这显然可以使用 dfs 解决。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,cnt,head[N];
int vis[N];//染色为 0 or 1
bool impossible;
struct edge{
    int to,next,color;
}e[N<<1];
inline void add(int x,int y,int co){
    e[++cnt].to=y;
    e[cnt].color=co;
    e[cnt].next=head[x];
    head[x]=cnt;
}
inline void dfs(int u,int color){
    if(impossible) return;
    vis[u]=color;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to,flag=e[i].color;
        if(flag==0){
            if(vis[v]==3){
                dfs(v,color^1); 
            }
            else{
                if(vis[v]==vis[u]) impossible=true; 
            }
        }
        else{
            if(vis[v]==3){
                dfs(v,color);
            }
            else{
                if(vis[v]!=vis[u]) impossible=true;
            }
        }
        if(impossible) return;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,co;i<=m;i++){
        scanf("%d%d%d",&x,&y,&co);
        add(x,y,co);add(y,x,co);
    }
    for(int i=1;i<=n;i++){
        vis[i]=3;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==3) dfs(i,0);
    }
    if(impossible){
        printf("Impossible");
        return 0;
    } 
    int ans=0;
    for(int i=1;i<=n;i++){
        if(vis[i]==0) ans++;
    }
    printf("%d\n",ans);
    for(int i=1;i<=n;i++){
        if(vis[i]==0) printf("%d ",i);
    }
    return 0;   
}