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;
}

Download