[1707번] 이분 그래프

#include <cstdio>
#include <vector>
#include <string.h>
#include <iostream>
using namespace std;

const int MAX = 20010;
vector<int> myGraph[MAX];
int check[MAX]; //check[]=0(방문하지 않음), 1(빨간색, 방문함), 2(파란색,방문함)

//파라미터 c를 통해 정점을 어떤 색으로 칠할지를 나타냄.
void dfs(int x, int c)
{
	check[x] = c;

	for(int i = 0; i < myGraph[x].size(); i++)
	{
		int y = myGraph[x][i];
		if(check[y] == 0)
		{
			dfs(y, 3-c);
		}

	}
}

int main()
{
	int testcase;
	int n,m;
	scanf("%d", &testcase);
	while(testcase--)
	{
		scanf("%d %d", &n, &m);
		//초기화
		for(int i = 1; i <= n; i++)
		{
			myGraph[i].clear();
			check[i] = 0;
		}
		
		for(int i = 0; i < m; i++)
		{
			int a,b;
			scanf("%d %d", &a, &b);
			myGraph[a].push_back(b);
			myGraph[b].push_back(a);
		}

		for(int i = 1; i <= n; i++)
		{
			if(check[i] == 0)
			{
				dfs(i, 1);
			}
		}

		//모든 정점과 간선에 대해서 간선의 양끝점의 색이 같으면 false, 다르면 true
		bool result = true;
		for(int i = 1; i <= n; i++)
		{
			for(int j = 0 ; j < myGraph[i].size(); j++)
			{
				int k = myGraph[i][j];
				if(check[i] == check[k])
				{
					result = false;
				}
			}
		}

		printf("%s\n", result? "YES":"NO");
	}

	return 0;
}