242. Bipartite graph determination

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  or  No  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;
}

Detailed explanation ：https://blog.csdn.net/li13168690086/article/details/81506044?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164465340716780274127071%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164465340716780274127071&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-81506044.pc_search_result_cache&utm_term=%E4%BA%8C%E5%88%86%E5%9B%BE%E5%88%A4%E5%AE%9A&spm=1018.2226.3001.4187