5268 | 2023-04-24 21:42:56 | k_balint | Turista járatok | cpp14 | Accepted 100/100 | 141ms | 65580 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 | 21284 KiB | ||||
2 | Accepted | 17ms | 23408 KiB | ||||
subtask2 | 10/10 | ||||||
3 | Accepted | 10ms | 21824 KiB | ||||
4 | Accepted | 9ms | 22032 KiB | ||||
5 | Accepted | 10ms | 22248 KiB | ||||
6 | Accepted | 10ms | 22088 KiB | ||||
7 | Accepted | 10ms | 22356 KiB | ||||
subtask3 | 10/10 | ||||||
8 | Accepted | 10ms | 22300 KiB | ||||
9 | Accepted | 9ms | 22560 KiB | ||||
10 | Accepted | 10ms | 22884 KiB | ||||
11 | Accepted | 10ms | 23112 KiB | ||||
12 | Accepted | 14ms | 24660 KiB | ||||
subtask4 | 10/10 | ||||||
13 | Accepted | 18ms | 26164 KiB | ||||
14 | Accepted | 10ms | 23048 KiB | ||||
15 | Accepted | 12ms | 23152 KiB | ||||
16 | Accepted | 13ms | 23228 KiB | ||||
17 | Accepted | 141ms | 64480 KiB | ||||
18 | Accepted | 48ms | 31576 KiB | ||||
19 | Accepted | 64ms | 34348 KiB | ||||
20 | Accepted | 52ms | 32092 KiB | ||||
subtask5 | 10/10 | ||||||
21 | Accepted | 17ms | 25708 KiB | ||||
22 | Accepted | 9ms | 23836 KiB | ||||
23 | Accepted | 9ms | 23944 KiB | ||||
24 | Accepted | 9ms | 24172 KiB | ||||
25 | Accepted | 93ms | 48104 KiB | ||||
26 | Accepted | 16ms | 25392 KiB | ||||
27 | Accepted | 14ms | 25648 KiB | ||||
subtask6 | 60/60 | ||||||
28 | Accepted | 9ms | 24072 KiB | ||||
29 | Accepted | 9ms | 24252 KiB | ||||
30 | Accepted | 10ms | 24448 KiB | ||||
31 | Accepted | 10ms | 24468 KiB | ||||
32 | Accepted | 12ms | 24856 KiB | ||||
33 | Accepted | 13ms | 25160 KiB | ||||
34 | Accepted | 16ms | 26008 KiB | ||||
35 | Accepted | 16ms | 26060 KiB | ||||
36 | Accepted | 16ms | 26000 KiB | ||||
37 | Accepted | 141ms | 65580 KiB | ||||
38 | Accepted | 52ms | 32324 KiB | ||||
39 | Accepted | 50ms | 32464 KiB | ||||
40 | Accepted | 48ms | 32456 KiB | ||||
41 | Accepted | 48ms | 32492 KiB | ||||
42 | Accepted | 48ms | 32480 KiB | ||||
43 | Accepted | 48ms | 32448 KiB | ||||
44 | Accepted | 48ms | 32460 KiB | ||||
45 | Accepted | 63ms | 35260 KiB | ||||
46 | Accepted | 48ms | 32516 KiB | ||||
47 | Accepted | 48ms | 32536 KiB | ||||
48 | Accepted | 52ms | 32352 KiB | ||||
49 | Accepted | 50ms | 32584 KiB | ||||
50 | Accepted | 48ms | 32544 KiB |