1707번_이분그래프

문제 출처 : https://www.acmicpc.net/problem/1707

팁 : 같은 그룹끼리 연결되면 안 된다

 

<C++ Code>

 

#include<iostream>
#include<vector>
#include<string.h>
#define MAX 20001
using namespace std;
vector<int> a[MAX];
int co[MAX];
 
 
void dfs(int x,int c)
{
    if(co[x]!=0) return ;
    co[x]=c;
    for(int i=0;i<a[x].size();i++)
    {
        int y=a[x][i];
        if(co[y]==0)
        {
            dfs(y,3-c);
        }
    }
}
 
int main(void)
{
 
    int k;
    cin>>k;
    while(k--)
    {
        
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        {
            a[i].clear();
            
            co[i]=0;
        }
        
    for(int i=0;i<m;i++)
    {
        int q,w;
        cin>>q>>w;
        a[q].push_back(w);
        a[w].push_back(q);
    }
    for(int i=1;i<=n;i++)
    {
        if(co[i]==0)
        {
            dfs(i,1);
        }
    }
    bool find=true;
    for(int i=1;i<=n;i++)
    {
        for(int t=0;t<a[i].size();t++)
        {
            int j=a[i][t];
            if(co[i]==co[j])
            {
                find=false;
            }
        }
    }
    if(find)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
}
 
    return 0;
    
}