えとー、こんなもんかの。
#define SET_3
using System;
using System.Collections.Generic;
using System.Linq;
namespace DAG {
struct bridge {
public char fr;
public char to;
public bridge(char f, char t) { fr = f; to = t; }
}
class Program
{
static void Main() {
List<bridge> path = new List<bridge>
#if SET_1
{
new bridge('A','B'),
new bridge('B','C'),
new bridge('A','C'),
new bridge('A','D'),
new bridge('C','D'),
};
#elif SET_2
{
new bridge('A','B'),
new bridge('A','C'),
new bridge('B','C'),
new bridge('B','D'),
new bridge('D','A'),
new bridge('D','C'),
};
#elif SET_3
{
new bridge('A','B'),
new bridge('B','C'),
new bridge('C','D'),
new bridge('D','E'),
new bridge('E','F'),
new bridge('F','G'),
new bridge('G','H'),
new bridge('H','F'),
};
#endif
while ( true ) {
// 表示
path.ForEach(item => Console.WriteLine("{0}->{1}", item.fr, item.to));
Console.WriteLine();
// 入口/出口セットを作る
var froms = (from item in path select item.fr).Distinct();
var tos = (from item in path select item.to).Distinct();
// 入口/出口セットの一方にあって他方にないものをremoveに
// symmetrc-diference に相当するもんがなさげなんで"X-Y と Y-X の和集合"で代用
var remove = Enumerable.Union(froms.Except(tos), tos.Except(froms));
if ( remove.Count() == 0 ) break;
// removeに含まれない橋を抽出する
path = (from item in path
where !(remove.Contains(item.fr) || remove.Contains(item.to))
select item).ToList();
}
Console.WriteLine(path.Count() == 0 ? "DAG!!" : "cyclic!!");
}
}
}