-
Notifications
You must be signed in to change notification settings - Fork 1
/
Program.cs
95 lines (81 loc) · 2.67 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
namespace CyclesInGraph
{
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Dictionary<char, List<char>> graph = new Dictionary<char, List<char>>();
FillTheGraph(graph);
SortedList<char, int> predecessors = new SortedList<char, int>();
FindPredecessors(graph, predecessors);
bool nodeRemoved = true;
foreach (var node in predecessors.Keys)
{
while (nodeRemoved)
{
nodeRemoved = false;
//foreach (var node in predecessors.Keys)
//{
if (predecessors[node] <= 1)
{
foreach (var child in graph[node])
{
if (predecessors.ContainsKey(child))
{
predecessors[child]--;
}
}
predecessors.Remove(node);
nodeRemoved = true;
break;
}
//}
}
}
Console.WriteLine("Acyclic: {0}", predecessors.Count == 0 ? "Yes" : "No");
}
private static void FillTheGraph(Dictionary<char, List<char>> graph)
{
while (true)
{
string line = Console.ReadLine();
if (string.IsNullOrEmpty(line))
{
break;
}
char node = line[0];
char child = line[4];
if (!graph.ContainsKey(node))
{
graph.Add(node, new List<char>());
}
graph[node].Add(child);
if (!graph.ContainsKey(child))
{
graph.Add(child, new List<char>());
}
graph[child].Add(node);
}
}
private static void FindPredecessors(Dictionary<char, List<char>> graph, SortedList<char, int> predecessors)
{
foreach (var node in graph.Keys)
{
if (!predecessors.ContainsKey(node))
{
predecessors.Add(node, 0);
}
foreach (var child in graph[node])
{
if (!predecessors.ContainsKey(child))
{
predecessors.Add(child, 0);
}
predecessors[child]++;
}
}
}
}
}