1302021-01-17 11:52:32Valaki2Parti (75 pont)cpp14Accepted 75/75168ms30736 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;
}
SubtaskSumTestVerdictTimeMemory
base75/75
1Accepted0/06ms11612 KiB
2Accepted0/075ms20836 KiB
3Accepted3/36ms12232 KiB
4Accepted3/34ms12236 KiB
5Accepted3/34ms12240 KiB
6Accepted3/36ms12620 KiB
7Accepted3/36ms12636 KiB
8Accepted4/46ms12580 KiB
9Accepted4/47ms12632 KiB
10Accepted4/48ms12768 KiB
11Accepted4/46ms12660 KiB
12Accepted4/47ms12808 KiB
13Accepted4/412ms12940 KiB
14Accepted4/49ms13236 KiB
15Accepted4/472ms21556 KiB
16Accepted4/490ms23768 KiB
17Accepted4/4104ms26552 KiB
18Accepted4/4122ms28948 KiB
19Accepted4/4145ms29964 KiB
20Accepted4/4155ms30736 KiB
21Accepted4/4168ms30696 KiB
22Accepted4/44ms14068 KiB