-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
95 lines (90 loc) · 3.11 KB
/
Program.cs
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
84
85
86
87
88
89
90
91
92
93
94
95
//使用染色方法,将图中相邻的节点染成不同颜色。染色图中如果发现相邻节点与当前节点颜色相同则返回false。否则返回true。
using System;
using System.Collections.Generic;
namespace PossibleBipartition
{
class Program
{
static void Main(string[] args)
{
int N = 5;
int[][] dislikes = new int[4][]
{
new []{1, 2},
new []{3, 4},
new []{4, 5},
new []{3, 5}
};
}
class Person
{
public int Id { get; set; }
public int Color { get; set; }
public List<Person> Dislikes { get; set; }
public Person(int x)
{
Id = x;
Dislikes = new List<Person>();
}
}
public bool PossibleBipartition_BFS(int N, int[][] dislikes)
{
var graph = new Person[N];
for (int i = 0; i < graph.Length; i++)
graph[i] = new Person(i);
foreach (var dislike in dislikes)
{
var person1 = graph[dislike[0] - 1];
var person2 = graph[dislike[1] - 1];
person1.Dislikes.Add(person2);
person2.Dislikes.Add(person1);
}
var queue = new Queue<Person>();
for (int i = 0; i < N; i++)
{
if (graph[i].Color != 0) continue;
graph[i].Color = 1;
queue.Enqueue(graph[i]);
while (queue.Count != 0)
{
var curPerson = queue.Dequeue();
foreach (var nextPerson in curPerson.Dislikes)
{
if (nextPerson.Color == curPerson.Color) return false;
if (nextPerson.Color != 0) continue;
nextPerson.Color = -curPerson.Color;
queue.Enqueue(nextPerson);
}
}
}
return true;
}
public bool PossibleBipartition_DFS(int N, int[][] dislikes)
{
var graph = new Person[N];
for (int i = 0; i < graph.Length; i++)
graph[i] = new Person(i);
foreach (var dislike in dislikes)
{
var person1 = graph[dislike[0] - 1];
var person2 = graph[dislike[1] - 1];
person1.Dislikes.Add(person2);
person2.Dislikes.Add(person1);
}
for (int i = 0; i < N; i++)
if (graph[i].Color == 0 && !DFS(graph[i], 1, graph))
return false;
return true;
}
private bool DFS(Person person, int color, Person[] graph)
{
person.Color = color;
foreach (var nextPerson in person.Dislikes)
{
if (nextPerson.Color == person.Color) return false;
if (nextPerson.Color == 0 && !DFS(nextPerson, -color, graph)) return false;
}
return true;
}
}
}