[Luogu 2341] HAOI2006 受欢迎的牛

智能推的水题，一看是省选题就给做了，做一半才发现 Tarjan 算法忘干净了。

Tarjan 求出SCC，算出每一个 SCC 包含原图的点数（size）以及新图上的出度（out）

并不用建图，Tarjan 时记一下 SCC 编号和 size，缩点时记录 out 就好了。

若存在唯一出度为 \(0\) 的 SCC，则这个 SCC 中所有的牛都是明星，即明星数量为这个 SCC 的 out。

否则答案为 \(0\)。

#include <algorithm>

#include <cstdio>

#include <stack>

using std::min;

using std::stack;

const int MAXN=10010,MAXM=50010;

bool exist[MAXN];

int n,m,cnt,num,sum,head[MAXN],DFN[MAXN],low[MAXN],SCC[MAXN],size[MAXN],out[MAXN];

stack<int> st;

struct edge

{

	int nxt,to;

	edge(int nxt=0,int to=0):nxt(nxt),to(to){}

}e[MAXM];

void AddEdge(int u,int v)

{

	e[++cnt]=edge(head[u],v),head[u]=cnt;

}

void Tarjan(int u)

{

	st.push(u),exist[u]=1,DFN[u]=low[u]=++num;

	for(int i=head[u],v;i;i=e[i].nxt)

		if(!DFN[v=e[i].to])

			Tarjan(v),low[u]=min(low[u],low[v]);

		else if(exist[v])

			low[u]=min(low[u],DFN[v]);

	if(DFN[u]==low[u])

	{

		++sum;

		for(int t;u!=t;)

			exist[t=st.top()]=0,st.pop(),++size[SCC[t]=sum];

	}

}

void Shrink(void)

{

	for(int u=1;u<=n;++u)

		for(int i=head[u],v;i;i=e[i].nxt)

			if(SCC[u]^SCC[v=e[i].to])

				++out[SCC[u]];

}

int Ans(void)

{

	int ans=0;

	for(int i=1;i<=sum;++i)

		if(!out[i])

			if(ans)

				return 0;

			else

				ans=size[i];

	return ans;

}

int main(int argc,char *argv[])

{

	scanf("%d %d",&n,&m);

	for(int i=1,u,v;i<=m;++i)

	{

		scanf("%d %d",&u,&v);

		AddEdge(u,v);

	}

	for(int i=1;i<=n;++i)

		if(!DFN[i])

			Tarjan(i);

	Shrink();

	printf("%d\n",Ans());

	return 0;

}

谢谢阅读。

巴特西

[Luogu 2341] HAOI2006 受欢迎的牛

[Luogu 2341] HAOI2006 受欢迎的牛

最新文章

热门文章