时间戳

首页 > 技术文章 > 洛谷 P2341 【受欢迎的牛】

洛谷 P2341 【受欢迎的牛】

qqq1112 2019-07-16 15:20 原文

 

思路：因为奶牛的爱慕关系具有传递性，所以每个环(强连通分量)里的奶牛是互相喜欢的。那么我们可以用到Tarjan算法把每个强连通分量找出，并缩点，把每个强连通分量都缩成一个点(当前缩点里的奶牛都是互相喜欢的)。这样一来，这个图就变成了一个DAG(有向无环图)。然后我们只需要统计每个缩点的出度就好了，如果一个点有出度&&我们知道这个图是一个DAG，所以这个强连通分量(这个缩点)里的奶牛就不可能被这个缩点所连出去的缩点里的奶牛所喜欢(这是无环图——DAG)。综上所述，我们只需要统计一下有多少个没有出度的强连通分量就好了，但有多个没有出度的强连通分量也不行，因为这样就会有两多群群奶牛不喜欢别的奶牛，使得奶牛们无法收到其他奶牛(这多群奶牛)的喜欢，这样就不行了 。

画一张图形象一下：

code ：

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 const int MAX = 5e4 + 1;
 5 stack < int > pru;
 6 int n, m, low[MAX], dfn[MAX], head[MAX], vis[MAX], col[MAX], sum[MAX], color, num, z, out[MAX], ans, cnt;
 7 struct node
 8 {
 9     int next, to;
10 }stu[MAX];
11 inline void add(int x, int y)
12 {
13     stu[++num].next = head[x];;
14     stu[num].to = y;
15     head[x] = num;
16     return;    
17 }
18 inline void tarjan(int u)//Tarjan算法模板，这里用于缩点 
19 {
20     low[u] = dfn[u] = ++z;
21     vis[u] = 1;
22     pru.push(u);
23     for(register int i = head[u]; i; i = stu[i].next)
24     {
25         int k = stu[i].to;
26         if(!vis[k])
27         {
28             tarjan(k);
29             low[u] = min(low[u], low[k]);
30         }
31         else if(!col[k])
32         {
33             low[u] = min(low[u], dfn[k]);
34         }
35     }
36     if(low[u] == dfn[u])
37     {
38         col[u] = ++color;
39         ++sum[color];//当前强连通分量里的奶牛的个数++ 
40         while(pru.top() != u)
41         {
42             col[pru.top()] = color;
43             ++sum[color];//当前强连通分量里的奶牛的个数++
44             pru.pop();
45         }
46         pru.pop();
47     }
48     return;
49 }
50 signed main()
51 {
52     scanf("%d %d", &n, &m);
53     for(register int i = 1, x, y; i <= m; ++i)
54     {
55         scanf("%d %d", &x, &y);
56         add(y, x);//建反向边，把统计出度变为统计入度，更加方便一些 
57     }
58     for(register int i = 1; i <= n; ++i)
59     {
60         if(!vis[i])
61         {
62             tarjan(i);
63         }
64     }
65     for(register int u = 1; u <= n; ++u)//循环每个结点的出度(这里是入度，因为建的是反向边) 
66     {
67         for(register int i = head[u]; i; i = stu[i].next)
68         {
69             int k = stu[i].to;//因为建的是反向边，所以i其实是k的出度 
70             if(col[k] != col[u])//颜色不相同就代表不在一个强连通分量里 
71             {
72                 ++out[col[k]];//所以k的颜色(及包含k的那个强连通分量)就不能选了(这里标记为出度++)，至于为什么思路里有讲 
73             }
74         }
75     }
76     for(register int i = 1; i <= color; ++i)//枚举每种颜色(每个强连通分量) 
77     {
78         if(!out[i])//要是没有出度(及当前强连通分量中没有奶牛喜欢别的奶牛) 
79         {
80             ++cnt;//记录有几个强连通分量的缩点没有出度 
81             ans = sum[i];//注意，这里是sum[i]，因为i点只是当前强连通分量的缩点，真正被所有奶牛都喜欢的奶牛个数其实是这个强连通分量的大小(及当前强连通分量中奶牛的个数) 
82         }
83     }
84     if(cnt == 1)//必须只有一个强连通分量没有出度，如果有多个也不行，因为这样那两个强连通分量里的奶牛都是不互相喜欢的 
85     {
86         printf("%d", ans);
87     }
88     else
89     {
90         printf("0");//没有奶牛被所有奶牛喜欢 
91     }
92     return 0;
93 }

 

推荐阅读