1

几个月前，我参加了一场关于 CodeForces 的比赛，从那以后我一直在尝试不同的解决方案来解决它。

该问题基本上由包含有向图的节点和边的输入组成。基本上，如果：A 指向 B，B 指向 C，C 指向 D，那么我们可以说 A 也指向 C，并且 D。B 也是如此，指向 D。你得到这个想法。

我现在的问题是，我尝试了一些不同的解决方案，其中一些有效但被时间限制卡住了。另一个是我提高效率的最佳尝试，但在某些测试中失败了。不幸的是，我不允许看测试。

这是我的代码的骨架，如果您不想在这里查看整个代码，下面会提到 TransitiveClosure() 函数：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace D.Find_Path3
{
    class Program
    {
        public class ReachabilityGraph
        {
            // placeholder
            public void TransitiveClosure() { }

            private Node[] _nodesArr;
            private HashSet<Node> _validNodes;
            private bool[,] _transitiveClosure;

            private int _nodes;
            private int _edges;

            public int Nodes { get { return _nodes; } }
            public int Edges { get { return _edges; } }

            public ReachabilityGraph(int nodes)
            {
                _nodes = nodes;

                _nodesArr = new Node[nodes];
                _validNodes = new HashSet<Node>();
                _transitiveClosure = new bool[nodes, nodes];
            }

            public void AddEdge(int u, int v)
            {
                if (_nodesArr[u] == null)
                    _nodesArr[u] = new Node(u);
                _validNodes.Add(_nodesArr[u]);

                if (_nodesArr[v] == null)
                    _nodesArr[v] = new Node(v);

                if (_nodesArr[u].AddChild(_nodesArr[v]))
                    ++_edges;
            }

            public bool IsConnected(int u, int v)
            {
                return _transitiveClosure[u, v];
            }

            class Node
            {
                private Lazy<HashSet<Node>> children = new Lazy<HashSet<Node>>(() => new HashSet<Node>());

                public int Value { get; private set; }
                public IEnumerable<Node> Children { get { return children.IsValueCreated ? children.Value : Enumerable.Empty<Node>(); } }
                public bool HasChildren { get { return children.IsValueCreated && children.Value.Count != 0; } }

                public Node(int value)
                {
                    Value = value;
                }

                public bool AddChild(Node u)
                {
                    return children.Value.Add(u);
                }

                public override bool Equals(object obj)
                {
                    var other = obj as Node;
                    return other != null && other.Value == Value;
                }

                public override int GetHashCode()
                {
                    return Value;
                }

                public override string ToString()
                {
                    return Value.ToString();
                }

                public static implicit operator int(Node n)
                {
                    return n.Value;
                }
            }
        }

        static void Main(string[] args)
        {
            // N: number of nodes
            // M: number of edges
            var NM = new int[2];
            GetIntsFromConsole(NM);

            var graph = new ReachabilityGraph(NM[0]);

            // add edges to graph
            var uv = new int[2];
            for (var i = 0; i < NM[1]; ++i)
            {
                GetIntsFromConsole(uv);
                graph.AddEdge(uv[0] - 1, uv[1] - 1);
            }

            graph.TransitiveClosure();

            // how many queries
            var Q = int.Parse(Console.ReadLine());
            for (var i = 0; i < Q; ++i)
            {
                GetIntsFromConsole(uv);
                Console.WriteLine(graph.IsConnected(uv[0] - 1, uv[1] - 1) ? "YES" : "NO");
            }
        }

        static void GetIntsFromConsole(int[] array)
        {
            var query = Console
                .ReadLine()
                .Split(' ')
                .Select(a => int.Parse(a));

            int i = 0;
            foreach (var item in query)
                array[i++] = item;
        }
    }
}

这是 TransitiveClosure 的有效但缓慢的尝试：

    public void TransitiveClosure()
    {
        foreach (var u in _validNodes)
        {
            var stack = new Stack<Node>();
            stack.Push(u);

            while (stack.Any())
            {
                var v = stack.Pop();
                _transitiveClosure[u, v] = true;

                foreach (var temp in v.Children)
                    if (!_transitiveClosure[u, temp])
                        stack.Push(temp);
            }
        }
    }

我也尝试递归地做，但这恰好是错误的，我不确定它背后的逻辑是什么部分是错误的：

            public void TransitiveClosure()
            {
                var stack = new Stack<Node>();

                foreach (var u in _validNodes)
                {
                    if (!_transitiveClosure[u, u])
                    {
                        TransitiveClosure(u, stack);
                        stack.Clear();
                    }
                }
            }

            private Stack<Node> TransitiveClosure(Node u, Stack<Node> subStack)
            {
                if (u.HasChildren && !_transitiveClosure[u, u])
                {
                    _transitiveClosure[u, u] = true;
                    var superStack = new Stack<Node>();

                    foreach (var child in u.Children)
                    {
                        var result = TransitiveClosure(child, subStack);

                        while (result.Any())
                        {
                            var v = result.Pop();

                            superStack.Push(v);
                            _transitiveClosure[u, v] = true;
                        }
                    }

                    subStack = superStack;
                }

                subStack.Push(u);
                return subStack;
            }

如果相关，我的代码使用邻接矩阵的其他尝试和其他可以在这里找到：http: //pastebin.com/A0a186V5。

感谢您对此的意见，以及我可以做些什么来使其更快。另外，如果你能告诉我我能做些什么来使我的第二次递归尝试工作。请原谅我在代码中缺少注释。

我不确定可以通过此实现的最佳复杂性是多少，因此请引导我走上正确的道路。也许还有其他一些我不知道的算法可以查看。

谢谢你，很抱歉这么长的帖子！

4

0 回答 0