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 |