1707번 이분 그래프

C언어 인접행렬로 구현하였다가, 메모리 초과가 떴다.

아마 C언어 인접행렬로 푸는 방법이 있을텐데, 나는 찾지 못 하였다.

그래서, C++과 C언어 이중 연결리스트로 풀었다.

또한, C언어 이중 연결리스트로 풀다가 처음에 시간 초과가 떴다.

이유는 내가 이중 연결리스트 삽입할 때에, 정렬된 순서로 삽입하려고 하니 초과가 난 것이다.

그래서, 그냥 삽입될 위치를 안 찾고, 첫 위치에 삽입하게 하니 통과 되었다.

예) 

정점 2에 3 5 4 1 순서로 삽입할 경우

시간 초과 : Graph[2] -> 1 -> 3 -> 4 -> 5 

정답 : Graph[2] -> 3 -> 5 -> 4 -> 1

이분 그래프

→ 서로 인접해 있는 노드들을 색깔로 표현했을 때, 서로 다른 색깔인 Graph 형태. 

    즉, 2가지의 색깔로 모든 노드들을 표현할 수 있다.

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

<C언어 이중 연결리스트 시간 초과> - 삽입될 위치를 찾을 때, 시간 많이 소모

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
 
typedef struct Node
{
    int data;
    struct Node * next;
    struct Node * before;
}Node;
 
Node * Graph[20002] = { NULL, }; // Header
 
int N = 0;
 
int V = 0, E = 0;
 
int color[20002] = { -1, };
 
void init()
{
    memset(color, -1, sizeof(color));
    memset(Graph, NULL, sizeof(Graph));
}
 
void Edge(int start, int end)
{
    Node * temp = (Node*)malloc(sizeof(Node));
 
    // 맨 처음
    if (Graph[start] == NULL)
    {
        temp->data = end;
        temp->next = NULL;
        temp->before = NULL;
 
        Graph[start] = temp;
 
        return;
    }
 
    // 맨 처음이 아니라면
    Node * front = Graph[start];
    Node * back = NULL;
 
    while (front != NULL && front->data <= end)
    {
        back = front;
        front = front->next;
    }
 
    if (front == NULL)
    {
        // 맨 마지막
        temp->data = end;
        temp->next = NULL;
        temp->before = back;
        back->next = temp;
    }
    else
    {
        // 처음 위치
        if (back == NULL)
        {
            temp->data = end;
            temp->next = front;
            temp->before = NULL;
 
            Graph[start] = temp;
 
            return;
        }
 
        // 중간
        // front
        temp->data = end;
        temp->next = front;
        front->before = temp;
 
        // back
        temp->before = back;
        back->next = temp;
    }
}
 
void DFS(int vertex, int nodeColor)
{
    color[vertex] = nodeColor;
 
    if (Graph[vertex] == NULL) return;
 
    Node * temp = Graph[vertex];
 
    while (temp)
    {
        int next = temp->data;
 
        if (color[next] == -1)
        {
            DFS(next, 3 - nodeColor);
        }
 
        temp = temp->next;
    }
}
 
int isBipartiteGraph()
{
    for (int i = 1; i <= V; i++)
    {
        if (Graph[i] == NULL) continue;
 
        Node * temp = Graph[i];
 
        while (temp)
        {
            int next = temp->data;
 
            if (color[i] == color[next]) return -1;
 
            temp = temp->next;
        }
    }
 
    return 1;
}
 
int main(void)
{
    scanf("%d", &N);
 
    for (int tc = 1; tc <= N; tc++)
    {
        init();
 
        scanf("%d %d", &V, &E);
 
        while (E--)
        {
            int from = 0, to = 0;
 
            scanf("%d %d", &from, &to);
 
            Edge(from, to);
            Edge(to, from);
        }
 
        for (int i = 1; i <= V; i++)
        {
            if (color[i] == -1)
            {
                DFS(i, 1);
            }
        }
 
        int ans = isBipartiteGraph();
 
        if (ans == 1) printf("YES\n");
        else printf("NO\n");
    }
 
    return 0;
}

<C언어 이중 연결리스트 통과> - 삽입할 때, 첫 위치에 삽입

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
 
typedef struct Node
{
    int data;
    struct Node * next;
    struct Node * before;
}Node;
 
Node * Graph[20002] = { NULL, }; // Header
 
int N = 0;
 
int V = 0, E = 0;
 
int color[20002] = { -1, };
 
void init()
{
    memset(color, -1, sizeof(color));
    memset(Graph, NULL, sizeof(Graph));
}
 
void Edge(int start, int end)
{
    Node * temp = (Node*)malloc(sizeof(Node));
 
    // 맨 처음
    if (Graph[start] == NULL)
    {
        temp->data = end;
        temp->next = NULL;
        temp->before = NULL;
        
        Graph[start] = temp;
 
        return;
    }
    
    // 그냥 첫 위치
    temp->data = end;
    temp->next = Graph[start];
    temp->before = NULL;
 
    Graph[start] = temp;
}
 
void DFS(int vertex, int nodeColor)
{
    color[vertex] = nodeColor;
 
    if (Graph[vertex] == NULL) return;
 
    Node * temp = Graph[vertex];
 
    while (temp)
    {
        int next = temp->data;
 
        if (color[next] == -1)
        {
            DFS(next, 3 - nodeColor);
        }
 
        temp = temp->next;
    }
}
 
int isBipartiteGraph()
{
    for (int i = 1; i <= V; i++)
    {
        if (Graph[i] == NULL) continue;
 
        Node * temp = Graph[i];
 
        while (temp)
        {
            int next = temp->data;
 
            if (color[i] == color[next]) return -1;
 
            temp = temp->next;
        }
    }
 
    return 1;
}
 
int main(void)
{
    scanf("%d", &N);
 
    for (int tc = 1; tc <= N; tc++)
    {
        init();
 
        scanf("%d %d", &V, &E);
 
        while (E--)
        {
            int from = 0, to = 0;
 
            scanf("%d %d", &from, &to);
 
            Edge(from, to);
            Edge(to, from);
        }
 
        for (int i = 1; i <= V; i++)
        {
            if (color[i] == -1)
            {
                DFS(i, 1);
            }
        }
 
        int ans = isBipartiteGraph();
 
        if (ans == 1) printf("YES\n");
        else printf("NO\n");
    }
 
    return 0;
}

<C++>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
vector<int> v[20002];
 
int color[20002] = { -1, };
 
int V = 0, E = 0;
 
void DFS(int vertex, int nodeColor)
{
    color[vertex] = nodeColor;
 
    for (auto next : v[vertex])
        if (color[next] == -1) DFS(next, 3 - nodeColor);
}
 
void init()
{
    memset(color, -1, sizeof(color));
 
    for (int i = 1; i <= V; i++)
        if (!v[i].empty()) v[i].clear();
}
 
bool isBipartiteGraph()
{
    for (int i = 1; i <= V; i++)
        for (auto next : v[i])        
            if (color[i] == color[next]) return false;
 
    return true;
}
 
int main(void)
{
    int from = 0, to = 0;
    int K = 0;
 
    scanf("%d", &K);
 
    for (int tc = 1; tc <= K; tc++)
    {
        init();
 
        scanf("%d %d", &V, &E);
 
        while (E--)
        {
            scanf("%d %d", &from, &to);
 
            v[from].push_back(to);
            v[to].push_back(from);
        }
 
        for (int i = 1; i <= V; i++)
        {
            if (color[i] == -1)
            {
                DFS(i, 1); // 색깔은 1부터 시작
            }
        }
 
        if (isBipartiteGraph()) printf("YES\n");
        else printf("NO\n");
    }
 
    return 0;
}