1707 이분 그래프

https://www.acmicpc.net/problem/1707

DFS로 노드를 탐색해가면서 마킹표시를 해준다. 이전 노드와 색이 같으면 이분그래프가 아니라고 판정한다.

#include <stdio.h>
#define V 20050
#define E 200050
 
struct NODE
{
    int node;
    struct NODE *next;
};
 
NODE HEAD[V],POOL[E*2];
int t,n,m,u,v,cnt,ans,visit[V];
 
void init(int n)
{
    cnt=0;
    ans=1;
    for(int i=1;i<=n;i++)
    {
        HEAD[i].next=NULL;
        visit[i]=0;
    }
}
 
void make(int u,int v)
{
    NODE *node=&POOL[cnt++];
    node->node=v;
    node->next=HEAD[u].next;
    HEAD[u].next=node;
}
 
void dfs(int n,int c)
{
    if(ans==0) return;
    visit[n]=c;
    for(NODE *ptr=HEAD[n].next;ptr;ptr=ptr->next)
    {
        int node=ptr->node;
        if(visit[node]==c)
        {
            ans=0;
            return;
        }
        else if(visit[node]==0)
            dfs(node,3-c);
    }
}
 
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        init(n);
        while(m--)
        {
            scanf("%d %d",&u,&v);
            make(v,u);
            make(u,v);
        }
        for(int i=1;i<=n;i++)
            if(visit[i]==0)
                dfs(i,1);
        printf("%s\n",ans?"YES":"NO");
    }
    return 0;
}