ListWeaver - WINNER

The winning code is shown below:

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace Orcomp 
{ 
    public class ListWeaver<T>
    { 
        public ListWeaver() 
        { 
            Yarns = new List<IList<T>>(); 
        } 

        public List<IList<T>> Yarns { get; set; }

        public bool CanWeave(IList<T> yarn)
        { 
            if (yarn == null)
                return false;

            List<IList<T>> yarns = Yarns.ToList(); 
            yarns.Add(yarn); 

            if (Walk(yarns) != null)
                return true;
            else 
                return false;
        } 

        public List<T> Weave() 
        { 
            return Walk(Yarns); 
        } 

        private List<T> Walk(List<IList<T>> yarns)
        { 
            var edges = new Dictionary<T, HashSet<T>>(); 
            foreach (var yarn in yarns)
            { 
                for (int i = 1; i < yarn.Count; i++)
                { 
                    if (!edges.ContainsKey(yarn[i])) 
                        edges[yarn[i]] = new HashSet<T>(); 
                    edges[yarn[i]].Add(yarn[i - 1]); 
                } 
            } 

            var path = new List<T>(edges.Count); 
            var seen = new HashSet<T>(); 

            var valid = yarns.Where(yarn => yarn.Count > 0).Select(yarn => yarn.Last()).All(node => Walk(node, path, edges, seen));
            if (valid) 
                return path; 
            else 
                return null;
        } 

        private bool Walk(T root, List<T> path, Dictionary<T, HashSet<T>> edges, HashSet<T> seen_all)
        { 
            var seen_now = new HashSet<T>(); 
            var to_visit = new LinkedList<KeyValuePair<T, bool>>(); 
            to_visit.AddLast(new KeyValuePair<T, bool>(root, false)); 

            while (to_visit.Count > 0)
            { 
                var last = to_visit.Last.Value; 
                var node = last.Key; 
                var drop = last.Value; 
                to_visit.RemoveLast(); 

                if (drop) 
                { 
                    path.Add(node); 
                    seen_now.Remove(node); 
                    continue; 
                } 

                if (seen_now.Contains(node)) 
                    return false;

                if (seen_all.Contains(node)) 
                    continue; 

                seen_all.Add(node); 
                seen_now.Add(node); 

                to_visit.AddLast(new KeyValuePair<T, bool>(node, true)); 
                if (edges.ContainsKey(node)) 
                    foreach (var edge in edges[node].Reverse())
                        to_visit.AddLast(new KeyValuePair<T, bool>(edge, false)); 
            } 

            return true; 
        } 
    } 
}

Feedback and Improvement:

The winning code runs efficiently in O(V+E) and makes very good use of HashSets and Dictionaries. (i.e. the time it takes to solve all benchmark tests is the same whether the lists are reversed or not, and the last two highly connected graphs solve efficiently in the same amount of time.) Well Done!

There is actually not much I can think of to improve on the code, however I would like to introduce another approach and start a new competition  for anyone who can solve this problem efficiently using an adjacency matrix representation of the graph using sparse matrices.

Some preliminary work suggests that if the adjacency matrix can be transformed into an upper triangular matrix a solution exists to the ListWeaver problem.

The following wikipedia page is a good starting point:
- Wikipeida - Adjacency matrix

You are allowed to use 3rd party open source libraries to represent the sparse matrices, if required.