[ABC286G] Unique Walk 题解

洛谷题目链接

At题目链接

这题一看就很欧拉路径，但是怎么做呢？

如果只有关键边，那么连通图首先会变成一堆连通块，这时只需要分别对每个连通块进行欧拉路径判断，但是对于不属于欧拉路径的连通块，很难对加上非关键边的情况进行扩展。

如果只有非关键边，那么连通图还是变成一堆连通块，但是这些连通块全部都是合法的，这样方便扩展。

如果一个关键边连接的两端点是一个连通块内的，那么这条关键边显然可以做到只经过一次，也就是在一个连通块内的关键边就不用考虑了；

那么剩下的关键边连接起来是一个无向连通图，此时做一遍裸的欧拉路径即可。

const int N=2e5+10;
int n,m,k;
int fa[N],vis[N],deg[N];
struct node {
	int l,r;
}a[N];

int find(int x) {
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]); 
}

void merge(int x,int y) {
	int fx=find(x),fy=find(y);
	if(fx!=fy) fa[fx]=fy;
}

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) cin>>a[i].l>>a[i].r;
	cin>>k;
	for(int i=1;i<=k;i++) {
		int p; cin>>p; vis[p]=1;
	}
	for(int i=1;i<=m;i++) {
		if(!vis[i]) merge(a[i].l,a[i].r);
	}
	for(int i=1;i<=m;i++) {
		if(vis[i]) {
			int id1=find(a[i].l),id2=find(a[i].r);
			if(id1!=id2) {
				deg[id1]++; deg[id2]++;
			}
		}
	}
	int cnt=0; 
	for(int i=1;i<=n;i++) if(deg[i]%2!=0) cnt++;
	if(cnt==0||cnt==2) cout<<"Yes";
	else cout<<"No"; 
	
	return 0;
}