问通过寻找顶点和边从连通图中移除圈

EN

function countEdgesAndVertices(directions, callback) {
    var turtle = [0, 0],
        vertices = {},
        revisit = false,
        edgeCount = 0,
        delta = {l: [-1, 0], r: [1, 0], u: [0, -1], d: [0, 1]},
        opposite = {l: 'r', r: 'l', u: 'd', d: 'u'},
        oppositeDir = '';
    vertices[turtle.join(',')] = true;
    directions.split('').forEach(function(dir) {
        if (!delta[dir]) return; // ignore invalid characters
        // Move turtle in given direction
        turtle[0] += delta[dir][0];
        turtle[1] += delta[dir][1];
        // Call caller's callback function with this vertex
        if (callback) callback(turtle);
        vertexId = turtle.join(',');
        // If this created a new edge, count it
        if (!vertices[vertexId] || !revisit && dir != oppositeDir) edgeCount++;
        // Remember whether we were here before
        revisit = vertices[vertexId];
        // Add vertice to set
        vertices[vertexId] = true;
        // Remember direction, so we wont count a move
        // in the opposite direction as a new edge
        oppositeDir = opposite[dir];
    });
    return {
        edges: edgeCount,
        vertices: Object.keys(vertices).length
    }
}

// IO
var input = document.querySelector('input');
var output = document.querySelector('span');
var canvas = document.querySelector('canvas');
var canvasContext;

// Drawing routines
function canvasDrawTo(vertex) {
    var scale = canvas.height/10;
    console.log('line to ', vertex[0],vertex[1]);
    canvasContext.lineTo(vertex[0]*scale,vertex[1]*scale);
    canvasContext.stroke();
}

function canvasClear(vertex) {
    canvas.width = canvas.width; // not nice, but this resets canvas
    canvasContext = canvas.getContext("2d");
    canvasContext.translate(canvas.width/2,canvas.height/2);
    canvasContext.beginPath();
    canvasContext.lineTo(0,0);
}

function update() {
    canvasClear();
    var result = countEdgesAndVertices(input.value, canvasDrawTo);
    output.textContent = 'Vertices: ' + result.vertices +
        '; Edges: ' + result.edges + 
        '; Non-divisable cycles: ' + (result.edges - result.vertices + 1);
};

// call update on any input change:
input.oninput = update;
// call update on load
update();

String of directions (u=up,d=down,l=left,r=right):<br>
<input type="text" size="40" value="uldrdddurulurdrdluurdur"><br>
Result: <span></span><br>
<canvas width="200" height="100"></canvas>