130 2021. 01. 17 11:52:32 Valaki2 Parti (75 pont) cpp14 Elfogadva 75/75 168ms 30736 KiB
#include <bits/stdc++.h>
using namespace std;

int n, ksz;
vector<int> g[100001];
vector<int> g2[100001];
vector<bool> volt(100001, false);
vector<bool> volt2(100001, false);
vector<int> top;
vector<int> scc(100001);

void dfs(int x) {
    if(volt[x]) return;
    volt[x] = true;
    for(int i : g[x]) dfs(i);
    top.push_back(x);
}

void dfs2(int y) {
    if(volt2[y]) return;
    volt2[y] = true;
    for(int i : g2[y]) dfs2(i);
    scc[y] = ksz;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int a, b;
        cin >> a >> b;
        g[i].push_back(a);
        g[i].push_back(b);
        g2[a].push_back(i);
        g2[b].push_back(i);
    }
    for(int i = 1; i <= n; ++i) dfs(i);
    reverse(top.begin(), top.end());
    for(int cs : top) {
        //cout << cs << " ";
        if(!volt2[cs]) {
            ++ksz;
            dfs2(cs);
        }
    }
    /*cout << "\n";
    cout << ksz << "\n";
    for(int i = 1; i <= n; ++i) {
        cout << i << ": " << scc[i] << "\n";
    }*/
    vector<bool> joscc(1+ksz, true);
    for(int i = 1; i <= n; ++i) {
        int db = 0;
        for(int j = 0; j < g2[i].size(); ++j) {
            if(scc[g2[i][j]] == scc[i]) {
                ++db;
            }
        }
        if(db != 2) {
            joscc[scc[i]] = false;
        }
    }
    vector<int> cnt(1+ksz, 0);
    for(int i = 1; i <= n; ++i) {
        ++cnt[scc[i]];
    }
    int maxscc = 0, maxcnt = 0;
    for(int i = 1; i <= ksz; ++i) {
        if((maxscc == 0 || maxcnt < cnt[i]) && joscc[i]) {
            maxscc = i;
            maxcnt = cnt[i];
        }
    }
    cout << maxcnt << "\n";
    for(int i = 1; i <= n; ++i) {
        if(scc[i] == maxscc) {
            cout << i << " ";
        }
    }
    cout << "\n";
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 75/75
1 Elfogadva 0/0 6ms 11612 KiB
2 Elfogadva 0/0 75ms 20836 KiB
3 Elfogadva 3/3 6ms 12232 KiB
4 Elfogadva 3/3 4ms 12236 KiB
5 Elfogadva 3/3 4ms 12240 KiB
6 Elfogadva 3/3 6ms 12620 KiB
7 Elfogadva 3/3 6ms 12636 KiB
8 Elfogadva 4/4 6ms 12580 KiB
9 Elfogadva 4/4 7ms 12632 KiB
10 Elfogadva 4/4 8ms 12768 KiB
11 Elfogadva 4/4 6ms 12660 KiB
12 Elfogadva 4/4 7ms 12808 KiB
13 Elfogadva 4/4 12ms 12940 KiB
14 Elfogadva 4/4 9ms 13236 KiB
15 Elfogadva 4/4 72ms 21556 KiB
16 Elfogadva 4/4 90ms 23768 KiB
17 Elfogadva 4/4 104ms 26552 KiB
18 Elfogadva 4/4 122ms 28948 KiB
19 Elfogadva 4/4 145ms 29964 KiB
20 Elfogadva 4/4 155ms 30736 KiB
21 Elfogadva 4/4 168ms 30696 KiB
22 Elfogadva 4/4 4ms 14068 KiB