受欢迎的奶牛

受欢迎的奶牛
首先使用tarjan算法， 把强连通分量都转换成一个点，最重要的是把整个复杂图化简成简单图之后，咋才能看出来那个受欢迎的牛呢？注意这里面找的时候是用简单图找的，也就是求完强连通分量之后的图，如果找到一头受欢迎的牛，实际上找到的是一个簇，这一个簇里面有很多头牛，然后这一堆牛都是受欢迎的牛；
我之前求的时候打算用广搜然后使用了下面这个dp方程：

dp[v]=dp[u]+weight[v]
1

一开始觉得挺对，因为在这个题前面我做了一个利用简单图求最长路的题，就是用的这个方法，emm，结果额不对；这个其实只要这个简单图有唯一的一个汇点，有两个及以上都不对
ac代码：

#include
using namespace std;
const int length = 1e4 + 5;
int dfn[length];
int low[length];
int color[length];
int siz[length];
int degree[length];
int in_stack[length];
int dp[length];
int cnt = 1;
int res = 1;
stack<int> s;
vector<vector<int>> edge(length);
vector<vector<int>> edget(length);
vector<pair<int, int>> edge_before;
void tarjan(int cur)
{
	dfn[cur] = cnt++;
	low[cur] = dfn[cur];
	in_stack[cur] = 1;
	s.push(cur);
	for (int j : edge[cur])
	{
		if (!dfn[j])
		{
			tarjan(j);
			low[cur] = min(low[cur], low[j]);
		}
		else if (in_stack[j])
		{
			low[cur] = min(low[cur], dfn[j]);//这块不用low[j]的原因是怕low[j]那个点不在栈里面
		}
	}
	if (dfn[cur] == low[cur])
	{
		while (s.top() != cur)
		{
			color[s.top()] = res;
			in_stack[s.top()] = 0;
			s.pop();
		}
		color[s.top()] = res;
		in_stack[s.top()] = 0;
		s.pop();
		res++;
	}
}
int main(void)
{
	int n, m;
	scanf_s("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf_s("%d%d", &a, &b);
		edge_before.push_back({ a,b });
	}
	sort(edge_before.begin(), edge_before.end(), [](pair<int,int> &a1,pair<int,int> &a2) {
		if (a1.first == a2.first)return a1.second < a2.second;
		else return a1.first < a2.first;
	});
	unique(edge_before.begin(), edge_before.end());
	for (auto j: edge_before)
	{
		int a = j.first;
		int b = j.second;
		edge[a].push_back(b);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!dfn[i])tarjan(i);
	}
	for (int i = 1; i <= n; i++)
	{
		siz[color[i]]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++)
	{
		for(int j:edge[i])
		{
			if (color[j]!=color[i])
			{
				edget[color[i]].push_back(color[j]);
				degree[color[i]]++;//找出度
			}
		}
	}
	int yh = 0;
	int t = -1;
	for (int i = 1; i <res; i++)
	{
		if (degree[i] == 0)
		{
			yh++;
			t = i;
		}
	}
	if (yh > 1)
		printf("0");
	else
		printf("%d", siz[t]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104