ENET - Mạng điện
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,ans,s,t,isCut[1010],child[1010],ok[1010],vs[1010];
int low[1010],num[1010],step,d[1010],e[1010];
vector <int> a[1010];
void visit(int x)
{
low[x]=num[x]=++step;
for (int i=0;i<int(a[x].size());i++)
{
int y=a[x][i];
if (y==d[x]) continue;
if (num[y]) low[x]=min(low[x],num[y]);
else d[y]=x, visit(y), low[x]=min(low[x],low[y]);
}
}
void bfs(int x,int cut,int d[])
{
for (int i=1;i<=n;i++) d[i]=0;
queue <int> q;
q.push(x); d[x]=1; d[cut]=1;
if (x==cut) return;
while (!q.empty())
{
x=q.front(); q.pop();
for (int i=0;i<int(a[x].size());i++)
{
int y=a[x][i];
if (!d[y]) d[y]=1, q.push(y);
}
}
}
int connected(int x,int y)
{
vs[x]=1;
if (x==y) return 1;
for (int i=0;i<int(a[x].size());i++)
if (!vs[a[x][i]] && connected(a[x][i],y))
return 1;
return 0;
}
int main()
{
int m,x,y;
cin >> n >> m >> s >> t;
while (m--) cin >> x >> y, a[x].push_back(y), a[y].push_back(x);
if (!connected(s,t))
{
cout << 0 << endl;
return 0;
}
for (int i=1;i<=n;i++)
if (!d[i]) visit(i);
for (int i=1;i<=n;i++) child[d[i]]++;
for (int i=1;i<=n;i++)
if (d[i] && !isCut[d[i]])
if (low[i]>=num[d[i]] && (d[d[i]] || child[d[i]]>1))
isCut[d[i]]=1;
for (int i=1;i<=n;i++) ok[i]=1;
for (int i=1;i<=n;i++)
if (isCut[i])
{
bfs(s,i,d);
bfs(t,i,e);
for (int j=1;j<=n;j++) ok[j]&=(d[j]|e[j]);
}
for (int i=1;i<=n;i++) ans+=ok[i];
cout << ans << endl;
for (int i=1;i<=n;i++)
if (ok[i]) cout << i << endl;
}