【luogu P2341 [HAOI2006]受欢迎的牛】题解

题解报告：https://www.luogu.org/problemnew/show/P2341

我们把图中的强连通分量缩点，然后只有出度为0的牛是受欢迎的，这样如果出度为0的牛只有一个，说明受所有牛欢迎。否则出度为0只是受一些牛欢迎。

#include <stack>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 100000 + 10;

struct edge{

	int next, to, from, len;

}e[maxn<<2];

int head[maxn], cnt;

int n, m, color[maxn], tong[maxn], du[maxn], num, tim, ans, tmp;

int dfn[maxn], low[maxn];

bool vis[maxn];

stack<int> s;

void add(int u, int v)

{

	e[++cnt].from = u;

	e[cnt].to = v;

	e[cnt].next = head[u];

	head[u] = cnt;

}

void tarjan(int x)

{

	dfn[x] = low[x] = ++tim;

	s.push(x); vis[x] = 1;

	for(int i = head[x]; i != -1; i = e[i].next)

	{

		int v = e[i].to;

		if(!dfn[v])

		{

			tarjan(v);

			low[x] = min(low[x], low[v]);

		}

		else if(vis[v])

		{

			low[x] = min(low[x], low[v]);

		}

	}

	if(dfn[x] == low[x])

	{

		color[x] = ++num;

		vis[x] = 0;

		while(s.top() != x)

		{

			color[s.top()] = num;

			vis[s.top()] = 0;

			s.pop();

		}

		s.pop();

	}

}

int main()

{

	memset(head, -1, sizeof(head));

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

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

	{

		int u, v;

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

		add(u,v);

	}

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

		if(!dfn[i]) tarjan(i);

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

	{

		for(int j = head[i]; j != -1; j = e[j].next)

		{

			int v = e[j].to;

			if(color[v] != color[i])

			{

				du[color[i]]++;

			}

		}

		tong[color[i]]++;

	}

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

	{

		if(du[i] == 0)

		{

			tmp++;

			ans = tong[i];

		}

	}

	if(tmp == 0)

	{

		printf("0");

		return 0;

	}

	if(tmp == 1)

	{

		printf("%d",ans);

		return 0;

	}

	if(tmp > 1)

	{

		printf("0");

		return 0;

	}

}

巴特西

【luogu P2341 [HAOI2006]受欢迎的牛】题解

最新文章

热门文章

巴特西

【luogu P2341 [HAOI2006]受欢迎的牛】 题解

最新文章

热门文章

【luogu P2341 [HAOI2006]受欢迎的牛】题解