C# problem transformed to N-component graph (N-island problem)
\n## Original problem transformation\n\nEach symbol in the input string put in compliance with a cell\n\n        |---n ---|---n ---|\n        |        |        
\n## Original problem transformation\n\nEach symbol in the input string put in compliance with a cell\n```\n        |---n ---|---n ---|\n        |        |        |\n        n   \'/\'  n   \'\\\'  n\n        |        |        |\n        |___n ___|___n ___|\n        |        |        |\n        n   \'\\\'  n   \'/\'  n\n        |        |        |\n        |___n ___|___n ___|\n```\nWe put a graph node in the middle of each border of cell\n\n\nEach two graph node could be connected if they are located in adjacent borders, and they are not separated by a slash\n    \n\nFor example here \n```\n|----n1--|\n|     /  |\nn2   /   n4\n|   /    |\n|__/_n3__|\n```\nn1 and n2 - connected\nn3 and n4 - connected\nn2 and n3 - not connected\nn1 and n4 - not connected\n\n## Algorithm\n\nNo we have to calculate number of connected component with UnionFind https://en.wikipedia.org/wiki/Disjoint-set_data_structure\n\n## Complexity\n\nO(N*log(n)) \n\nwhere \nN - total number of symbols in input text\n\n## Code \n\n### UnionFind implementation\n\n```csharp\n\nusing System;\nusing System.Collections.Generic;\n\n\nstruct NodeId\n{\n    public NodeId(int row, int column)\n    {\n        Row=row;\n        Column = column;\n    }\n    public int Row;\n    public int Column;\n}\n\nclass Node\n{\n    public NodeId Id;\n    public Node? Parent;\n    public int Rank;\n}\n\nclass DisjointSet\n{\n    public HashSet<Node> DistinctRoots {get;} = new HashSet<Node>();\n    public Dictionary<NodeId, Node> Nodes {get;} = new Dictionary<NodeId, Node>();\n    \n    // Get the root node and flatten the tree\n    private static Node Find(Node node){\n        if(node.Parent == null)\n        {\n            return node;\n        }\n        var res = Find(node.Parent);\n        node.Parent = res;\n        return res;\n    }\n    public void AddUnconnected(NodeId nodeId)\n    {\n        var node = new Node(){Id = nodeId, Parent=null, Rank=0};\n        Nodes[nodeId] = node;\n        DistinctRoots.Add(node);\n    }\n    public void Union(NodeId a, NodeId b)\n    {\n        var nodeA = Nodes[a];\n        var nodeB = Nodes[b];\n        var parentA = Find(nodeA);\n        var parentB = Find(nodeB);\n        \n        if(parentA == parentB)\n        {\n            return;\n        }\n        else\n        {\n            var (rootParent, childParent) = parentA.Rank > parentB.Rank? (parentA, parentB):(parentB, parentA);\n            if (rootParent.Rank == childParent.Rank)\n            {\n                rootParent.Rank = rootParent.Rank + 1;\n            }\n            childParent.Parent = rootParent;\n            DistinctRoots.Remove(childParent);\n\n        }\n\n    }\n}\n\n\n```\n\n## Build the graph (connect nodes)\n\n\n```csharp\n\n\nvar inputStrings = new string[]{@"/ \\",@"\\ /"};\n\n\nvar disjointSet = new DisjointSet();\n\n// Centers of horizontal edges\nfor(var row=0; row < inputStrings.Length + 1; row++)\nfor(var column=0; column < inputStrings[0].Length; column++)\n{\n    disjointSet.AddUnconnected(new NodeId(){Row=row*2, Column=column});\n}\n\n// Centers of vertical edges\nfor(var row=0; row < inputStrings.Length; row++)\nfor(var column=0; column < inputStrings[0].Length + 1; column++)\n{\n    disjointSet.AddUnconnected(new NodeId(){Row=row*2+1, Column=column});\n}\n\n// Build the graph\nforeach(var inputString in inputStrings.Select((inputString, rowIndex) => (rowIndex: rowIndex, value: inputString)))\n{\n    var verticalEdgesRowId = inputString.rowIndex*2 + 1;\n    var horisonatalUpperEdgesRowId = inputString.rowIndex*2;\n    var horisonatalLowerEdgesRowId = inputString.rowIndex*2 + 2;\n    foreach(var cell in inputString.value.Select((symbol, index) => (columnIndex:index, symbol: symbol)) )\n    {\n        var centerOfLeftEdge = new NodeId(row: verticalEdgesRowId, column: cell.columnIndex);\n        var centerOrRightEdge = new NodeId(row: verticalEdgesRowId, column: cell.columnIndex+1);\n        var centerOfUpperEdge = new NodeId(row: horisonatalUpperEdgesRowId, column: cell.columnIndex);\n        var centerOfLowerEdge = new NodeId(row: horisonatalLowerEdgesRowId, column: cell.columnIndex);\n\n        switch(cell.symbol)\n        {\n            case \' \':\n                disjointSet.Union(centerOfLeftEdge, centerOfUpperEdge);\n                disjointSet.Union(centerOfLeftEdge, centerOfLowerEdge);\n                disjointSet.Union(centerOrRightEdge, centerOfUpperEdge);\n                disjointSet.Union(centerOrRightEdge, centerOfLowerEdge);\n                break;\n            case \'\\\\\':\n                disjointSet.Union(centerOfLeftEdge, centerOfLowerEdge);\n                disjointSet.Union(centerOrRightEdge, centerOfUpperEdge);\n                \n                break;\n            case \'/\':\n                disjointSet.Union(centerOfLeftEdge, centerOfUpperEdge);\n                disjointSet.Union(centerOrRightEdge, centerOfLowerEdge);\n                \n                break;\n            default:\n                throw new NotImplementedException();\n        }\n    }\n}\n\nvar result = disjointSet.DistinctRoots.Count;\nConsole.WriteLine($"Result: {result}");\n\n\n```
['Union Find']