TopCoder SRM598: TPS

public class TPS {
    static int[] GetDegrees(string[] linked) {
        var n = linked.Length;
        var deg = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (linked[i][j] == 'Y') {
                    deg[j]++;
                }
            }
        }
        return deg;
    }

    String[] Shrink(string[] linked) {
        int n = linked.Length;
        var deg = GetDegrees(linked);
        var newLinked = linked.Select(a => a.ToCharArray()).ToArray();
        bool yet = true;
        while (yet) {
            yet = false;
            for (int i = 0; i < n; i++) {
                if (deg[i] == 2) {
                    var adjacent = Enumerable.Range(0, n).Where(x => newLinked[i][x] == 'Y').ToArray();
                    int a = adjacent[0];
                    int b = adjacent[1];
                    newLinked[i][a] = newLinked[a][i] = 'N';
                    newLinked[i][b] = newLinked[b][i] = 'N';
                    newLinked[a][b] = newLinked[b][a] = 'Y';
                    deg[i] = 0;
                    yet = true;
                }
            }
        }

        return newLinked.Select(a => new string(a)).ToArray();
    }

    public int minimalBeacons(string[] linked) {
        linked = Shrink(linked);
        int n = linked.Length;
        var deg = GetDegrees(linked);
        int nodeNum = deg.Count(d => d == 1);
        if (nodeNum == 2)
            return 1;
        for (int i = 0; i < n; i++) {
            if (deg[i] <= 1) continue;
            int adjacentNodeNum = 0;
            for (int j = 0; j < n; j++) {
                if (linked[i][j] == 'Y' && deg[j] == 1) {
                    adjacentNodeNum++;
                }
            }
            if (adjacentNodeNum >= 1) {
                if (deg[i] != 2)
                    nodeNum--;
            }
        }
        return nodeNum;
    }
}