Submission #7793264


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef vector<int> vi;

bool tarjan(vi e[], int x, bool st[], int disc[], int &dn, vi &t) {
    int dmax = -1, dmaxp = -1;
    for (int y : e[x]) {
        if (st[y] && disc[y] > dmax) {
            dmax = disc[y];
            dmaxp = y;
        }
    }

    disc[x] = ++dn;
    st[x] = true;

    if (dmaxp != -1) {
        int y = dmaxp;
        while (y != x) {
            t.push_back(y);

            int dmax = -1, dmaxz = -1;
            for (int z : e[y]) {
                if (st[z] && disc[z] > dmax) {
                    dmax = disc[z];
                    dmaxz = z;
                }
            }
            y = dmaxz;
        }
        t.push_back(x);
        return true;
    }

    for (int y : e[x]) {
        if (!disc[y]) {
            bool f = tarjan(e, y, st, disc, dn, t);
            if (f) {
                return true;
            }
        }
    }

    st[x] = false;
    return false;
}

int main() {
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vi e[n];
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        e[a].push_back(b);
    }

    bool st[n];
    memset(st, false, sizeof(st));
    int disc[n];
    memset(disc, 0, sizeof(disc));
    int dn = 0;
    for (int i = 0; i < n; i++) {
        if (!disc[i]) {
            vi t;
            if (tarjan(e, i, st, disc, dn, t)) {
                cout << t.size() << endl;
                for (int x : t) {
                    cout << x + 1 << endl;
                }
                return 0;
            }
        }
    }

    cout << -1 << endl;

    return 0;
}

Submission Info

Submission Time
Task F - Pure
User fdironia
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1785 Byte
Status
Exec Time 3 ms
Memory 384 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 Sample_01.txt, Sample_02.txt, Sample_03.txt
Subtask1 600 / 600 Sample_01.txt, Sample_02.txt, Sample_03.txt, case_01.txt, case_02.txt, case_03.txt, case_04.txt, case_05.txt, case_06.txt, case_07.txt, case_08.txt, case_09.txt, case_10.txt, case_11.txt, case_12.txt, case_13.txt, case_14.txt, case_15.txt, case_16.txt, case_17.txt, case_18.txt, case_19.txt, case_20.txt, case_21.txt, case_22.txt, case_23.txt, case_24.txt, case_25.txt, case_26.txt, case_27.txt, case_28.txt, case_29.txt, case_30.txt
Case Name Status Exec Time Memory
Sample_01.txt 1 ms 256 KB
Sample_02.txt 1 ms 256 KB
Sample_03.txt 1 ms 256 KB
case_01.txt 2 ms 256 KB
case_02.txt 2 ms 256 KB
case_03.txt 2 ms 384 KB
case_04.txt 2 ms 384 KB
case_05.txt 2 ms 256 KB
case_06.txt 2 ms 384 KB
case_07.txt 2 ms 256 KB
case_08.txt 2 ms 384 KB
case_09.txt 2 ms 384 KB
case_10.txt 2 ms 256 KB
case_11.txt 2 ms 256 KB
case_12.txt 2 ms 256 KB
case_13.txt 2 ms 256 KB
case_14.txt 2 ms 256 KB
case_15.txt 2 ms 256 KB
case_16.txt 1 ms 256 KB
case_17.txt 1 ms 256 KB
case_18.txt 1 ms 256 KB
case_19.txt 1 ms 384 KB
case_20.txt 2 ms 384 KB
case_21.txt 2 ms 384 KB
case_22.txt 2 ms 384 KB
case_23.txt 1 ms 384 KB
case_24.txt 1 ms 384 KB
case_25.txt 3 ms 384 KB
case_26.txt 3 ms 384 KB
case_27.txt 3 ms 384 KB
case_28.txt 3 ms 384 KB
case_29.txt 3 ms 384 KB
case_30.txt 2 ms 384 KB