using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

    }

}

​

public class DirGraph : ICloneable

{

    public List<Node> Nodes{get;set;}

    public List<DirEdge> Edges{get;set;}

    public DirGraph(List<Node> nodes, List<DirEdge> edges)

    {

        Nodes = nodes;

        Edges = edges;

    }

    public object Clone()

    {

        var nodes = new List<Node>();

        foreach(var node in Nodes)

        {

            nodes.Add(new Node(node.ID));

        }

        var edges = new List<DirEdge>();

        foreach(var edge in Edges)

        {

            edges.Add(new DirEdge(edge.Weight, new Node(edge.Source.ID), new Node(edge.Destination.ID)));

        }

        return new DirGraph(nodes, edges);

    }

    public Arborescence GetArborescence(DirGraph graph, Node root)

    {

        DirGraph newGraph = (DirGraph)graph.Clone();

        newGraph.Edges.RemoveAll(e => e.Destination.ID == root.ID);

        newGraph.Edges = GetUniqueEdges(newGraph);

        var minEdges = GetMinEdges(newGraph);

        if(GetCycle(newGraph, minEdges, root) == null)

        {

            return new Arborescence(root, minEdges);

        }

    }

    public List<DirEdge> GetUniqueEdges(DirGraph graph)

    {

        graph.Edges.OrderBy(e => e.Source.ID);

        var uniqueEdges = new List<DirEdge>();

        uniqueEdges.Add(graph.Edges[0]);

        for(int i = 1; i < graph.Edges.Count; i++)

        {

            var edgeToCheck = graph.Edges[i];

            var lastEdge = uniqueEdges.Last();

            if(edgeToCheck.Source.ID == lastEdge.Source.ID

            && edgeToCheck.Destination.ID == lastEdge.Destination.ID

            && edgeToCheck.Weight < lastEdge.Weight)

            {

                uniqueEdges.Remove(lastEdge);

                uniqueEdges.Add(edgeToCheck);

            }

        }

        return uniqueEdges;

    }

    public List<DirEdge> GetMinEdges(DirGraph graph)

    {

        graph.Edges.OrderBy(e => e.Destination.ID);

        var minEdges = new List<DirEdge>();

        minEdges.Add(graph.Edges[0]);

        for(int i = 1; i < graph.Edges.Count; i++)

        {

            var edgeToCheck = graph.Edges[i];

            var lastEdge = minEdges.Last();

            if(edgeToCheck.Destination.ID == lastEdge.Destination.ID && edgeToCheck.Weight < lastEdge.Weight)

            {

                minEdges.Remove(lastEdge);

                minEdges.Add(edgeToCheck);

            }

        }

        return minEdges;

    }

    public List<Node> GetCycle(DirGraph graph, List<DirEdge> edges, Node root)

    {

        var cycle = new List<Node>();

        cycle = TraverseNodes(cycle);

    }

    public List<Node> TraverseNodes(List<Node> cycle)

    {

    }

}

​

public class Node

{

    public int ID{get;set;}

    public List<Node> Children{get;set;}

    public Node(int id)

    {

        ID = id;

        Children = new List<Node>();

    }

    public void AddChild(Node node)

    {

        Children.Add(node);

    }

}

​

public class DirEdge

{

    public int Weight{get;set;}

    public Node Source{get;set;}

    public Node Destination{get;set;}

    public DirEdge(int weight, Node source, Node destination)

    {

        Weight = weight;

        Source = source;

        Destination = destination;

    }

}

​

public class Arborescence

{

    public Node Root{get;set;}

    public List<DirEdge> Edges{get;set;}

    public Arborescence(Node root, List<DirEdge> edges)

    {

        Root = root;

        Edges = edges;

    }

    public int Weight

    {

        get{return Edges.Sum(e => e.Weight);}

    }

}

​

​