目录
原题截图:
题目大意:
主要思路:
注意事项(很多人再这个地方掉坑):
代码:
原题截图:
题目大意:
给你两个数组(A和B)长度都为n,然你求出一个01元组(设为x,长度为m) 使得 (i<=n)
主要思路:
如果你细细想一想,这题就很简单,我们可以发现,可以用图论的方式解决,将a[i]和b[i]之间连一条无向边,然后染色法(用0和1,边的两边染的颜色要不同),如果有两个颜色再同一点,就有问题,输出No,否则输出Yes。
注意事项(很多人再这个地方掉坑):
- 图不一定是连通的(也就是初始化成-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;
}