백준 1707문제

그래프 연결 문제로 linked  list 로 인접 행렬을 구현해서.. 연습용 문제

#include <stdio.h>
#include <iostream> 
#include <vector>
#include <cmath>
#include <string>
#include <set>
#include <queue>
#include <functional>
#include <algorithm>
#include <memory.h>
 
#pragma warning(disable : 4996)
using namespace std;
 
long long min_v, max_v;
 
#define MAX(a,b) a>b ? a:b
#define MIN(a,b) a>b ? b:a
 
 
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
 
int N;
 
vector<vector<int> > adj; // 인접리스트
//vector<int>color; // 인접리스트
short color[20002]; // 0은 아직 방문 X, -1 또는 1은 방문한 정점의 색
 
typedef struct _arr{
 
    int data;
 
    struct _arr *next;
    struct _arr *prev;
 
}Arr;
 
Arr *Graph[20001] = { 0, };
Arr temp_buf[2000001] = { 0, };
int NumCnt = -1;
 
int ac [20001] = { 0, };
 
void Init(){
 
    NumCnt = -1;
 
    memset(color, 0, sizeof (color));
    memset(Graph, 0, sizeof (Graph));
    memset(temp_buf, 0, sizeof (temp_buf));
    memset(ac, 0, sizeof (ac));
 
}
 
 
Arr * getListNode(void )
{
    NumCnt++;
    temp_buf[NumCnt].data = 0;
 
    temp_buf[NumCnt].next = &temp_buf[NumCnt];
    temp_buf[NumCnt].prev = &temp_buf[NumCnt];
 
    return &temp_buf[NumCnt];
}
 
 
Arr * appendListNode(Arr* list, int data)
{
    Arr * node = getListNode();
    node->data = data;
 
    if (list == NULL)
    {
        return node;
    }
    else
    {
        Arr* last = list->prev;
        last->next = node;
        list->prev = node;
        node->prev = last;
        node->next = list;
 
        return list;
    }
}
 
void Edge(int start, int end){
 
    Graph[start] = appendListNode(Graph[start], end);
    ac[start]++;
 
 
}
// @ret : false , true; 
// @int n : number of idx 
// @int c : color  1 or 1 , 0 --> 방문안한곳 
 
bool DFS(int n, int c) {
 
    color[n] = c;
    Arr *temp = Graph[n];
    int cnt = 0;
 
    while (temp && cnt < ac[n]){
 
        int next = temp->data;
 
        if (color[next] != 0 && color[next] == c)
            return false;
 
        if (color[next] == 0 ) {
            if (!DFS(next, c * -1))
                return false;
 
        }
 
        temp = temp->next;
        cnt++;
 
    }
 
    return true;
}
 
 
// size , @ret => non chk idx 
 
int chk_c(int adj_size){
 
    for (int i = 0; i < adj_size; i++)
    if (color[i] == 0) return i;
 
    //all done
    return -1;
}
 
int main() {
 
    int TC = 1;
    int V, E;
    bool ans = true;
    int a, b;
 
    //freopen("input.txt", "r", stdin); setbuf(stdout, NULL);
    cin >> TC;
 
 
    while (TC--){
 
        ans = true;
        cin >> V >> E;
        Init();
        
        // 인접리스트 저장
        for (int i = 0; i < E; i++) {
 
            cin >> a >> b;
            Edge(a, b);
            Edge(b, a);
        }
 
        for (int i = 0; i < V; i++)
        {
            if (color[i] == 0)
            {
                if (!DFS(i, 1)) {
                    ans = false;
                    break;
                }
            }
        }
 
        if (ans)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
 
}