898 2022. 01. 25 19:11:10 Babják Péter Elfogás cpp11 Elfogadva 50/50 50ms 12316 KiB
#include <bits/stdc++.h>
#define MAXN 20100
#define MAXM 100100
//start 18 19
using namespace std;
int n,m,st,en;
vector<int>adj[MAXN],path;
bool us[MAXN],red[MAXN],ct[MAXN],off[MAXN],enh[MAXN];
int el[MAXN],low[MAXN];
void dfs1(int v)
{
	path.push_back(v);
	us[v]=1;
	if(us[en]==1)return;
	for(int u:adj[v])
	{
		if(us[en]==1)break;
		if(us[u]==0)
		{
			dfs1(u);
		}
	}
	if(us[en]==1)return;
	path.pop_back();
}
int db=1;
void dfs(int v)
{
	int ch=0;
	us[v]=1;
	el[v]=db;db++;
	low[v]=el[v];
	for(int u:adj[v])
	{
		if(us[u]==0)
		{
			dfs(u);
			if(low[u]>=el[v] && enh[u]==1)ct[v]=1;
			low[v]=min(low[v],low[u]);
			enh[v]=max(enh[v],enh[u]);
			ch++;
		}
		else
		{
			low[v]=min(low[v],el[u]);
		}
	}
	if(v==st && ch>1)ct[st]=1;
	else ct[st]=0;
}
vector<int>ans;
void dfs2(int v)
{
	ans.push_back(v);
	us[v]=1;
	for(int u:adj[v])
	{
		if(us[u]==0 && ct[u]==0)dfs2(u);
	}
}
int main()
{
	cin>>n>>m>>st>>en;
	enh[en]=1;
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	dfs1(st);
	for(int p:path)red[p]=1;
	for(int i=0;i<=n;i++)us[i]=0;
	dfs(st);
	for(int i=1;i<=n;i++) us[i]=0;
	ct[st]=1;
	dfs2(en);
	cout<<ans.size()<<'\n';
	for(int u:ans)cout<<u<<" ";
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 2ms 2784 KiB
2 Elfogadva 0/0 8ms 4132 KiB
3 Elfogadva 2/2 1ms 2888 KiB
4 Elfogadva 2/2 3ms 3052 KiB
5 Elfogadva 2/2 2ms 3084 KiB
6 Elfogadva 2/2 2ms 3108 KiB
7 Elfogadva 3/3 2ms 3128 KiB
8 Elfogadva 3/3 2ms 3156 KiB
9 Elfogadva 3/3 4ms 3360 KiB
10 Elfogadva 3/3 4ms 3416 KiB
11 Elfogadva 3/3 6ms 3940 KiB
12 Elfogadva 3/3 8ms 4252 KiB
13 Elfogadva 3/3 8ms 4572 KiB
14 Elfogadva 3/3 8ms 4896 KiB
15 Elfogadva 3/3 9ms 5240 KiB
16 Elfogadva 3/3 35ms 7052 KiB
17 Elfogadva 3/3 37ms 7848 KiB
18 Elfogadva 3/3 37ms 8648 KiB
19 Elfogadva 3/3 37ms 9228 KiB
20 Elfogadva 3/3 50ms 12316 KiB