1213.cpp

#include <stdio.h>
#include <vector>
#include <functional>
#include <algorithm>
#include <cassert>

int main() {
    // freopen("input.txt", "rt", stdin);
    // freopen("output.txt", "wt", stdout);

    // Чтение графа, G - матрица смежности
    int nVert, type;
    scanf("%d %d", &nVert, &type);

    std::vector<std::vector<bool>> G(nVert, std::vector<bool>(nVert, false));
    for (int i = 0; i < nVert; ++i) {
        char buf[2001];
        scanf("%2000s", buf);
        for (int j = 0; j < nVert; ++j) {
            G[i][j] = (buf[j] == '+');
        }
    }
    // Топологическая сортировка вершин графа:
    std::vector<bool> used;
    used.assign(nVert, false);
    std::vector<int> order;
    for (int i = 0; i < nVert; ++i)
        if (!used[i]) {
            std::function<void(int)> dfs1 = [&dfs1, &used, &G, &order](int curr) {
                used[curr] = true;
                for (int next = 0; next < (int)G[curr].size(); ++next)
                    if (G[curr][next] && !used[next]) {
                        dfs1(next);
                    }
                order.push_back(curr);
            };
            dfs1(i);
        }
    // Получение компонент сильной связности в явном виде:
    used.assign(nVert, false);
    std::vector<std::vector<int>> components(1, std::vector<int>());
    for (int i = 0; i < nVert; ++i) {
        int v = order[nVert-1-i];
        if (!used[v]) {
            std::function<void(int)> dfs2 = [&dfs2, &G, &used, &components](int curr) {
                used[curr] = true;
                components.back().push_back(curr);
                for (int next = 0; next < (int)G[curr].size(); ++next)
                    if (G[next][curr] && !used[next])
                        dfs2(next);
            };
            dfs2(v);
            components.push_back(std::vector<int>());
        }
    }

    // Подсчет ответа в случае увеличения количества совершенных городов:
    std::vector<int> count(1+nVert, 0);
    {
        int sum = (int)components[0].size();
        for (int i = 1; i < (int)components.size(); ++i) {
            sum += components[i].size();
            if (sum != 2) {
                count[sum] += components[0].size() * components[i].size();
            }
        }
    }

    // Получение Гамильтонова пути:
    std::vector<int> path;
    for (const auto & v : components[0]) {
        if (path.empty()) {
            path.push_back(v);
        } else {
            auto it = path.begin();
            while (it != path.end() && G[*it][v]) {
                ++it;
            }
            path.insert(it, v);
        }
    }

    // Проверка того, что Гамильтонов путь был получен корректно (на всякий случай):
    for (int i = 1; i < (int)path.size(); ++i) {
        int prev = path[i-1], curr = path[i];
        assert(G[prev][curr]);
    }

    // Гамильтонов цикл:
    std::vector<int> cycle;
    { // Первоначальная подготовка к преобразования Гамильтонова пути в Гамильтонов цикл:
        int start = path[0], i;
        for (i = (int)path.size()-1; i >= 2; --i) {
            if (G[path[i]][start]) {
                break;
            }
        }
        cycle.insert(cycle.begin(), path.begin(), path.begin()+i+1);
        path.erase(path.begin(), path.begin()+i+1);
    }

    // Преобразование Гамильтонова пути к Гамильтонову циклу:
    for (auto st = path.begin(); st != path.end(); ) {
        auto it = cycle.begin();
        while (it != cycle.end() && G[*it][*st]) {
            ++it;
        }
        if (it != cycle.end()) {
            cycle.insert(it, path.begin(), st+1);
            path.erase(path.begin(), st+1);
            st = path.begin();
        } else {
            st++;
        }
    }

    if ((int)cycle.size() > 1) // Проверяем, что был найден цикл (на всякий случай)
        for (int i = 0, n = (int)cycle.size(); i < n; ++i) {
            assert(G[cycle[i]][cycle[(i+1) % n]]);
        }

    // Проход по ребрам Гамильтонова цикла с разворотом ребер на нем:
    if ((int)cycle.size() > 1) {
        G[cycle.front()][cycle.back()] = true;
        G[cycle.back()][cycle.front()] = false;
        int n = (int)cycle.size();
        std::vector<int> x(n, -1);
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                int a = cycle[i];
                int b = cycle[j];
                if (G[b][a]) {
                    x[i] = j;
                }
            }
        }
        bool wasBreaked = false;
        int max = 0;
        for (int i = 0; i < n; ++i) {
            max = std::max(max, x[i]);
            if (max <= i) {
                count[i+1]++;
                wasBreaked = true;
                break;
            }
        }
        assert(wasBreaked);

        G[cycle.front()][cycle.back()] = false;
        G[cycle.back()][cycle.front()] = true;

        for (int k = 0; k < n-1; ++k) {
            std::rotate(cycle.begin(), cycle.begin()+1, cycle.end());
            for (int i = 0; i+1 < n; ++i) {
                x[i] = x[i+1] - 1;
            }
            x[n-1] = -1;
            G[cycle.front()][cycle.back()] = true;
            G[cycle.back()][cycle.front()] = false;

            for (int i = 0; i < n; ++i) {
                int a = cycle[i];
                int b = cycle.back();
                if (G[b][a]) {
                    x[i] = n-1;
                }
            }

            bool wasBreaked = false;
            int max = 0;
            for (int i = 0; i < n; ++i) {
                max = std::max(max, x[i]);
                if (max <= i) {
                    count[i+1]++;
                    wasBreaked = true;
                    break;
                }
            }
            assert(wasBreaked);

            G[cycle.front()][cycle.back()] = false;
            G[cycle.back()][cycle.front()] = true;
        }
    }
    // Окончательно досчитываем ответ:
    std::vector<bool> is_first_component(nVert, false);
    for (auto & v : components[0]) {
        is_first_component[v] = true;
    }
    for (int i = 0; i < nVert; ++i) {
        for (int j = i+1; j < nVert; ++j) {
            if (!is_first_component[i] && !is_first_component[j]) {
                count[(int)components.front().size()]++;
            }
        }
    }
    int sum = 0;
    for (int i = 1; i <= nVert; ++i) {
        sum += count[i];
    }

    count[(int)components.front().size()] += nVert * (nVert-1)/2 - sum;
    // И выводим его:
    printf("%d\n", (int)components.front().size());
    for (int i = (type == 0 ? (int)components[0].size() : 0)+1; i <= nVert; ++i) {
        printf("%d ", count[i]);
    }
    return 0;
}