当前位置:网站首页>242. Bipartite graph determination
242. Bipartite graph determination
2022-07-07 07:35:00 【Recursions】
Given a with n A graph of vertices .
To dye every vertex on a graph , And make the adjacent vertices have different colors .
Ask if you can dye with up to two colors ? The title guarantees no double edges and self rings .
Input
- The first line is an integer n(1≤n≤1000), Represents the number of vertices
- Next, there are two integers in each line x and y, It means a vertex x and y There is a side between ,0≤x,y<n,x≠y
- With
EOF(end of file)
As the end of edge data
Output
Yes
orNo
Indicates whether two colors can be used for dyeing
Examples 1
Input
3 0 1 1 2 2 0
Output
No
#include<bits/stdc++.h>
using namespace std;
int n;
int color[1001];
vector<int>e[1001];
bool dfs(int v,int c)
{
color[v]=c;
for(int i=0;i<e[i].size();i++)
{
if(color[e[v][i]]==c)
return false;
if(color[e[v][i]]==0&&!dfs(e[v][i],-c))
return false;
}
return true;
}
int main()
{
while(cin>>n)
{
for(int i=0;i<n;i++)
{
int v1,v2;
cin>>v1>>v2;
e[v1].push_back(v2);
e[v2].push_back(v1);
}
for(int i=0;i<n;i++){
if(color[i]==0){
if(!dfs(i,1)){
cout<<"No"<<endl;
return 0;
}
}
}
cout<<"Yes"<<endl;
}
return 0;
}
边栏推荐
- mips uclibc 交叉编译ffmpeg,支持 G711A 编解码
- 1、 Go knowledge check and remedy + practical course notes youth training camp notes
- @component(““)
- 外包干了三年,废了...
- Outlier detection technology of time series data
- 身边35岁程序员如何建立起技术护城河?
- 按键精灵采集学习-矿药采集及跑图
- JS plot flot application - simple curve
- BGP experiment (1)
- Robot technology innovation and practice old version outline
猜你喜欢
4、 High performance go language release optimization and landing practice youth training camp notes
面试官:你都了解哪些开发模型?
BGP experiment (1)
Example of Pushlet using handle of Pushlet
抽丝剥茧C语言(高阶)指针进阶练习
Bindingexception exception (error reporting) processing
【Liunx】进程控制和父子进程
07_ Handout on the essence and practical skills of text measurement and geometric transformation
How to reduce inventory with high concurrency on the Internet
2、 Concurrent and test notes youth training camp notes
随机推荐
外包幹了三年,廢了...
[ANSYS] learning experience of APDL finite element analysis
2022-07-06:以下go语言代码是否会panic?A:会;B:不会。 package main import “C“ func main() { var ch chan struct
Deep learning Flower Book + machine learning watermelon book electronic version I found
Simple example of ros2 planning system plansys2
Determining the full type of a variable
L'externalisation a duré trois ans.
Readonly read only
Jenkins远程构建项目超时的问题
外包干了三年,废了...
Build personal website based on flask
【Liunx】进程控制和父子进程
About some details of final, I have something to say - learn about final CSDN creation clock out from the memory model
JS decorator @decorator learning notes
关于二进制无法精确表示小数
抽絲剝繭C語言(高階)數據的儲存+練習
Lm11 reconstruction of K-line and construction of timing trading strategy
JS plot flot application - simple curve
UWB learning 1
聊聊异步编程的 7 种实现方式