【题解】CF1470D Strange Housing
7KByte
·
·
题解
想了一个更简单的方法。
我们可以用归纳法。
对于前 n-1 个点，如果我们构造出了一种方案，那么现在考虑加入第 n 个点，如果与第 n 个点连边的点有一个染了色，那么当前点就不需要染色，否则当前点必定染色。
```cpp
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 300005
using namespace std;
int n,m,v[N],h[N],tot,in[N];
struct edge{int to,nxt;}e[N<<1];
void add(int x,int y){e[++tot].nxt=h[x];h[x]=tot;e[tot].to=y;}
queue<int>q;
void solve(){
scanf("%d%d",&n,&m);
rep(i,1,n)h[i]=0,v[i]=~0,in[i]=0;tot=0;
rep(i,1,m){
int x,y;scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
while(!q.empty())q.pop();
v[1]=in[1]=1;q.push(1);
while(!q.empty()){
int x=q.front();q.pop();
bool flag=true;
for(int i=h[x];i;i=e[i].nxt)if(~v[e[i].to])flag&=!v[e[i].to];
v[x]=flag;
for(int i=h[x];i;i=e[i].nxt)if(!in[e[i].to])in[e[i].to]=1,q.push(e[i].to);
}
rep(i,1,n)if(!in[i]){puts("NO");return ;}
puts("YES");int sum=0;
rep(i,1,n)sum+=v[i];
printf("%d\n",sum);
rep(i,1,n)if(v[i])printf("%d ",i);putchar('\n');
}
int main(){
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
```