AtCoder ABC周赛2023 11/4 (Sat) D题题解

目录

原题截图：

题目大意：

主要思路：

注意事项（很多人再这个地方掉坑）：

代码：

原题截图：

?

题目大意：

给你两个数组（A和B)长度都为n，然你求出一个01元组（设为x,长度为m) 使得?(i<=n)

主要思路：

如果你细细想一想，这题就很简单，我们可以发现，可以用图论的方式解决，将a[i]和b[i]之间连一条无向边，然后染色法（用0和1，边的两边染的颜色要不同），如果有两个颜色再同一点，就有问题，输出No，否则输出Yes。

注意事项（很多人再这个地方掉坑）：

1. 图不一定是连通的（也就是初始化成-1，遍历一下所有点，如果这个点是-1，就以这个点为开头，染色，然后继续遍历点）

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200010],b[200010];
vector<int> g[200010];
int color[200010];
int flag;
void dfs(int c, int u)
{
	color[c]=u;
	for(int i=0;i<g[c].size();i++)
	{
		if(color[g[c][i]] == -1)
		{
			dfs(g[c][i],1-u);
		}
		else if(color[g[c][i]] == color[c])
		{
			flag=1;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a[i];
		a[i]--;
	}
	for(int i=0;i<m;i++)
	{
		cin>>b[i];
		b[i]--;
	}
	for(int i=0;i<m;i++)
	{
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}
	for(int i=0;i<n;i++)
	{
		color[i]=-1;
	}
	for(int i=0;i<n;i++)
	{
		if(color[i] == -1)
		{
			dfs(i,0);	
		}
	}
	cout<<(flag?"No":"Yes");
    return 0;
}