题解 Strange Housing

传送门

首先想了黑白染色，发现不会染

其实可以考虑如何动态地维护出这个点集

发现题面里对不在点集之中的点之间的连边没有要求

所以考虑不断向图中加点，为了满足要求，每次取一个与当前新图中相连的点

若它与点集中的点有连边，那它不能选入点集

如果没有，那它必须选入点集，否则这个点不满足「通过开启边可达」的要求

但如何证明这样下去得到的点集一定满足「通过开启边可达」的要求呢？

发现加了「开启边」这个要求之后非点集中的点之间的连边就废了

那图就成了二分图了

而我们加边时所加的所有边构成一条链，这条链连通了所有点

得证

或者参考题解做法

Code:

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 300010

#define reg register int

#define ll long long

//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)

inline int read() {

	int ans=0, f=1; char c=getchar();

	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}

	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}

	return ans*f;

}

int n, m;

int head[N], size, fa[N], sta[N], top;

bool vis[N], vis2[N];

struct edge{int to, next;}e[N<<1];

inline void add(int s, int t) {edge* k=&e[++size]; k->to=t; k->next=head[s]; head[s]=size;}

inline int find(int p) {return fa[p]==p?p:fa[p]=find(fa[p]);}

void dfs(int u, int pa) {

	vis[u]=1;

	for (int i=head[u]; i; i=e[i].next)

		if (vis2[e[i].to]) goto jump;

	vis2[u]=1;

	sta[++top]=u;

	jump:

	for (int i=head[u]; i; i=e[i].next)

		if (!vis[e[i].to]) dfs(e[i].to, u);

}

signed main()

{

	int T;

	T=read();

	while (T--) {

		size=0; top=0;

		n=read(); m=read();

		memset(head, 0, sizeof(int)*(n+10));

		memset(vis, 0, sizeof(bool)*(n+10));

		memset(vis2, 0, sizeof(bool)*(n+10));

		for (reg i=1; i<=n; ++i) fa[i]=i;

		for (int i=1,u,v; i<=m; ++i) {

			u=read(); v=read();

			add(u, v); add(v, u);

			fa[find(u)]=find(v);

		}

		int u=find(1);

		for (int i=2; i<=n; ++i) if (find(i)!=u) {puts("NO"); goto loop;}

		puts("YES");

		dfs(1, 0);

		printf("%d\n", top);

		for (int i=1; i<=top; ++i) printf("%d ", sta[i]);

		printf("\n");

		loop: ;

	}

	return 0;

}

巴特西

题解 Strange Housing

最新文章

热门文章