1282021-01-17 11:22:15Valaki2Parti (75 pont)cpp14Futási hiba 0/751ms1200 KiB
#include <bits/stdc++.h>
using namespace std;

int n, ksz;
vector<int> g[100001];
vector<int> g2[1000001];
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ÖsszpontTesztVerdiktIdőMemória
base0/75
1Futási hiba0/01ms1132 KiB
2Futási hiba0/01ms1076 KiB
3Futási hiba0/31ms1196 KiB
4Futási hiba0/31ms1200 KiB
5Futási hiba0/31ms1200 KiB
6Futási hiba0/31ms1136 KiB
7Futási hiba0/31ms1196 KiB
8Futási hiba0/41ms1196 KiB
9Futási hiba0/41ms1132 KiB
10Futási hiba0/41ms1068 KiB
11Futási hiba0/41ms1068 KiB
12Futási hiba0/41ms1196 KiB
13Futási hiba0/41ms1196 KiB
14Futási hiba0/41ms1200 KiB
15Futási hiba0/41ms1200 KiB
16Futási hiba0/41ms1200 KiB
17Futási hiba0/41ms1196 KiB
18Futási hiba0/41ms1128 KiB
19Futási hiba0/41ms1200 KiB
20Futási hiba0/41ms1136 KiB
21Futási hiba0/41ms1196 KiB
22Futási hiba0/41ms1200 KiB