1240 | 2022-03-28 16:21:49 | k_balint | Turista járatok | cpp14 | Accepted 100/100 | 181ms | 78188 KiB |
#include <bits/stdc++.h>
using namespace std;
const int c=40004;
struct edge{
int v,id;
edge(int vv, int i){
v=vv; id=i;
}
edge(){
v=id=0;
}
};
int n,m,k;
vector<edge> adj[c];
int t[c],l[c];
bool used[10*c];
stack<int> s;
int tt; int cnt;
vector<int> comp[3*c];
int cut[c];
int ecmp[10*c];
bool good[3*c];
bool cut_cmp[3*c];
void new_comp(int id){
while(!s.empty() && s.top() != id){
int cur=s.top();
s.pop();
if(cur<=k) good[cnt]=1;
ecmp[cur]=cnt;
comp[cnt].push_back(cur);
}
if(!s.empty()){
int cur=s.top();
s.pop();
if(cur<=k) good[cnt]=1;
ecmp[cur]=cnt;
comp[cnt].push_back(cur);
}
++cnt;
}
vector<int> tree[3*c];
vector<edge> edges;
void dfs(int v, int p){
t[v]=l[v]=tt++;
bool children=0;
for(edge x:adj[v]){
if(x.id==p) continue;
if(!used[x.id]){
used[x.id]=1;
s.push(x.id);
}
if(!t[x.v]){
dfs(x.v,x.id);
l[v]=min(l[v],l[x.v]);
if(v==1?children:l[x.v]>=t[v]){
if(!cut[v]){
cut_cmp[cnt]=1;
cut[v]=cnt;
comp[cnt].push_back(v); ++cnt;
}
tree[cut[v]].push_back(cnt);
tree[cnt].push_back(cut[v]);
new_comp(x.id);
}
children=1;
}
else l[v]=min(l[v],t[x.v]);
}
if(cut[v] && p!=0){
edges.push_back(edge(cut[v],p));
}
if(v==1 && !s.empty()){
if(cut[v]){
tree[cut[v]].push_back(cnt);
tree[cnt].push_back(cut[v]);
}
new_comp(-1);
}
}
bool vis[3*c];
void dfs2(int v, bool g){
vis[v]=1; good[v]|=g;
for(int x:tree[v]){
if(!vis[x]){
dfs2(x,good[v]);
}
}
}
bool ans[c];
edge edg[10*c];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int a,b; cin>>a>>b;
edg[i]=edge(a,b);
adj[a].push_back(edge(b,i));
adj[b].push_back(edge(a,i));
}
tt=1; cnt=1;
dfs(1,0);
for(edge x:edges){
tree[x.v].push_back(ecmp[x.id]);
tree[ecmp[x.id]].push_back(x.v);
}
if(adj[1].empty()){
cout << 0 << endl;
return 0;
}
if(!cut[1]) dfs2(ecmp[adj[1][0].id],0);
else dfs2(cut[1],0);
for(int i=1;i<cnt;i++){
if(!good[i]) continue;
if(cut_cmp[i]){
ans[comp[i][0]]=1;
continue;
}
for(int x:comp[i]){
int a=edg[x].v;
int b=edg[x].id;
if(!cut[a]) ans[a]=1;
if(!cut[b]) ans[b]=1;
}
}
ans[1]=0;
int ans2=0;
for(int i=1;i<=n;i++){
if(ans[i]) ++ans2;
}
cout << ans2 << '\n';
for(int i=1;i<=n;i++){
if(ans[i]){
cout << i << ' ';
}
}
cout << endl;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 12ms | 21256 KiB | ||||
2 | Accepted | 19ms | 23268 KiB | ||||
subtask2 | 10/10 | ||||||
3 | Accepted | 10ms | 21460 KiB | ||||
4 | Accepted | 10ms | 21472 KiB | ||||
5 | Accepted | 9ms | 21468 KiB | ||||
6 | Accepted | 12ms | 21476 KiB | ||||
7 | Accepted | 10ms | 21488 KiB | ||||
subtask3 | 10/10 | ||||||
8 | Accepted | 9ms | 21484 KiB | ||||
9 | Accepted | 9ms | 21488 KiB | ||||
10 | Accepted | 9ms | 21508 KiB | ||||
11 | Accepted | 10ms | 21784 KiB | ||||
12 | Accepted | 14ms | 23212 KiB | ||||
subtask4 | 10/10 | ||||||
13 | Accepted | 17ms | 24816 KiB | ||||
14 | Accepted | 9ms | 21656 KiB | ||||
15 | Accepted | 10ms | 21876 KiB | ||||
16 | Accepted | 10ms | 21960 KiB | ||||
17 | Accepted | 181ms | 67036 KiB | ||||
18 | Accepted | 59ms | 34904 KiB | ||||
19 | Accepted | 76ms | 38908 KiB | ||||
20 | Accepted | 56ms | 37216 KiB | ||||
subtask5 | 10/10 | ||||||
21 | Accepted | 17ms | 30780 KiB | ||||
22 | Accepted | 10ms | 29044 KiB | ||||
23 | Accepted | 12ms | 29068 KiB | ||||
24 | Accepted | 12ms | 29220 KiB | ||||
25 | Accepted | 115ms | 56260 KiB | ||||
26 | Accepted | 17ms | 33576 KiB | ||||
27 | Accepted | 17ms | 33724 KiB | ||||
subtask6 | 60/60 | ||||||
28 | Accepted | 10ms | 32372 KiB | ||||
29 | Accepted | 10ms | 32408 KiB | ||||
30 | Accepted | 12ms | 32640 KiB | ||||
31 | Accepted | 13ms | 32756 KiB | ||||
32 | Accepted | 13ms | 33008 KiB | ||||
33 | Accepted | 17ms | 33288 KiB | ||||
34 | Accepted | 17ms | 34332 KiB | ||||
35 | Accepted | 17ms | 34484 KiB | ||||
36 | Accepted | 17ms | 34632 KiB | ||||
37 | Accepted | 181ms | 78188 KiB | ||||
38 | Accepted | 54ms | 45908 KiB | ||||
39 | Accepted | 54ms | 46960 KiB | ||||
40 | Accepted | 56ms | 47844 KiB | ||||
41 | Accepted | 57ms | 48768 KiB | ||||
42 | Accepted | 54ms | 49500 KiB | ||||
43 | Accepted | 57ms | 50452 KiB | ||||
44 | Accepted | 56ms | 51448 KiB | ||||
45 | Accepted | 83ms | 55568 KiB | ||||
46 | Accepted | 59ms | 53724 KiB | ||||
47 | Accepted | 57ms | 54656 KiB | ||||
48 | Accepted | 59ms | 55344 KiB | ||||
49 | Accepted | 57ms | 56380 KiB | ||||
50 | Accepted | 65ms | 57264 KiB |