CodingPractice/785.c at main · kimhedol00/CodingPractice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdbool.h>

bool isBipartite(int** graph, int graphSize, int* graphColSize){
	int8_t sides[graphSize];	//-1 : left, 0 : undefined, 1 : right
	memset( &sides, 0, sizeof (sides) );

	for (int i = 0; i < graphSize; i += 1){
		if (sides[i] != 0){
			continue;
		}

		int curSide = -1;

		int bfsQueue[graphSize];
		int get = 0, set = 0;

		sides[i] = curSide;
		bfsQueue[set] = i;
		set += 1;

		do {
			curSide = -curSide;
			for (int remain = set - get; remain > 0; remain -= 1){
				const int cur = bfsQueue[get];
				get += 1;

				for (int j = 0; j < graphColSize[cur]; j += 1){
					const int next = graph[cur][j];

					if (sides[next] == -curSide){
						return false;
					}

					if (0 == sides[next]){
						sides[next] = curSide;
						bfsQueue[set] = next;
						set += 1;
					}
				}
			}
		}while (get < set);
	}

	return true;
}

/*
Best Solution
bool DFS(int** graph, int graphSize, int* graphColSize, int depth[], int i, int parent){
    bool oddCycle = false;
    for(int j = 0; j < graphColSize[i]; j++){
        if(graph[i][j] == parent)
            continue;
        //printf("%d ", graph[i][j]);
        if(depth[graph[i][j]] != -1){
            int cycle = abs(depth[graph[i][j]] - depth[i]);
            if(cycle > 1 && (cycle % 2 == 0))
                return true;
            continue;
        }
        depth[graph[i][j]] = depth[i] + 1;
        oddCycle |= DFS(graph, graphSize, graphColSize, depth, graph[i][j], i);
    }
    return oddCycle;
}
bool isBipartite(int** graph, int graphSize, int* graphColSize){

    int depth[graphSize];
    for(int i = 0; i < graphSize; i++)
        depth[i] = -1;
    for(int i = 0; i < graphSize; i++){
        if(depth[i] != -1)
            continue;
        depth[i] = 0;
        bool flag = DFS(graph, graphSize, graphColSize, depth, i, -1);
        if(flag)
            return false;
        //printf("\n");
    }
    return true;
}
*/