8982022-01-25 19:11:10Babják PéterElfogáscpp11Accepted 50/5050ms12316 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;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/02ms2784 KiB
2Accepted0/08ms4132 KiB
3Accepted2/21ms2888 KiB
4Accepted2/23ms3052 KiB
5Accepted2/22ms3084 KiB
6Accepted2/22ms3108 KiB
7Accepted3/32ms3128 KiB
8Accepted3/32ms3156 KiB
9Accepted3/34ms3360 KiB
10Accepted3/34ms3416 KiB
11Accepted3/36ms3940 KiB
12Accepted3/38ms4252 KiB
13Accepted3/38ms4572 KiB
14Accepted3/38ms4896 KiB
15Accepted3/39ms5240 KiB
16Accepted3/335ms7052 KiB
17Accepted3/337ms7848 KiB
18Accepted3/337ms8648 KiB
19Accepted3/337ms9228 KiB
20Accepted3/350ms12316 KiB