231722026-01-16 15:37:44khn08Cseppkőbarlang (45 pont)cpp17Wrong answer 0/45560ms6356 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> g, gr;
vector<int> comp, indeg;
vector<bool> used;
vector<int> order;

// cella -> csúcs index
inline int id(int i, int j) {
    return (i - 1) * m + j;
}

// 1. DFS – sorrendhez
void dfs1(int v) {
    used[v] = true;
    for (int u : g[v])
        if (!used[u])
            dfs1(u);
    order.push_back(v);
}

// 2. DFS – komponenshez
void dfs2(int v, int c) {
    comp[v] = c;
    for (int u : gr[v])
        if (comp[u] == -1)
            dfs2(u, c);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    vector<vector<int>> t(n + 1, vector<int>(m + 1, 0));

    int N = n * m;
    g.assign(N + 1, {});
    gr.assign(N + 1, {});

    // input + gráf építés
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> t[i][j];
            if (t[i][j] == 0) continue;

            int v = id(i, j);

            // bal szomszéd
            if (j > 1 && t[i][j - 1] > 0) {
                int u = id(i, j - 1);
                if (t[i][j] >= t[i][j - 1]) {
                    g[u].push_back(v);
                    gr[v].push_back(u);
                }
                if (t[i][j] <= t[i][j - 1]) {
                    g[v].push_back(u);
                    gr[u].push_back(v);
                }
            }

            // felső szomszéd
            if (i > 1 && t[i - 1][j] > 0) {
                int u = id(i - 1, j);
                if (t[i][j] >= t[i - 1][j]) {
                    g[u].push_back(v);
                    gr[v].push_back(u);
                }
                if (t[i][j] <= t[i - 1][j]) {
                    g[v].push_back(u);
                    gr[u].push_back(v);
                }
            }
        }
    }

    // Kosaraju 1. lépés
    used.assign(N + 1, false);
    for (int v = 1; v <= N; v++)
        if (!used[v])
            dfs1(v);

    // Kosaraju 2. lépés
    comp.assign(N + 1, -1);
    int c = 0;
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int v = order[i];
        if (comp[v] == -1) {
            dfs2(v, c);
            c++;
        }
    }

    // komponens gráf indegree
    indeg.assign(c, 0);
    for (int v = 1; v <= N; v++) {
        for (int u : g[v]) {
            if (comp[v] != comp[u])
                indeg[comp[u]]++;
        }
    }

    // válasz
    vector<pair<int,int>> ans;
    for (int i = 0; i < c; i++) {
        if (indeg[i] == 0) {
            // keresünk egy csúcsot ebből az SCC-ből
            for (int v = 1; v <= N; v++) {
                if (comp[v] == i) {
                    int r = (v - 1) / m + 1;
                    int col = (v - 1) % m + 1;
                    ans.push_back({r, col});
                    break;
                }
            }
        }
    }

    cout << ans.size() << "\n";
    for (auto &p : ans)
        cout << p.first << " " << p.second << "\n";

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base0/45
1Wrong answer0/01ms512 KiB
2Wrong answer0/01ms316 KiB
3Wrong answer0/11ms316 KiB
4Wrong answer0/11ms316 KiB
5Wrong answer0/2250ms6356 KiB
6Wrong answer0/2331ms5520 KiB
7Wrong answer0/2273ms5700 KiB
8Wrong answer0/21ms392 KiB
9Wrong answer0/21ms316 KiB
10Wrong answer0/3497ms4720 KiB
11Wrong answer0/3300ms5556 KiB
12Wrong answer0/3234ms4660 KiB
13Wrong answer0/3225ms4500 KiB
14Time limit exceeded0/3560ms4480 KiB
15Wrong answer0/3367ms5168 KiB
16Wrong answer0/3280ms5276 KiB
17Wrong answer0/3388ms5172 KiB
18Wrong answer0/3386ms5172 KiB
19Wrong answer0/3430ms4964 KiB
20Wrong answer0/3312ms5428 KiB