蒙牛官网网站怎么做的/阿里指数查询官网

Link

传送门
题目

解题思路

先Tarjan，把牛进行捆绑
（在一个强连通分块中，如果一个牛是明星，那么其他的牛也一定是明星）

考虑明星的的条件

1. 在出度为0的强连通分块中
   (如果这个分块喜欢另一个分块的牛，因为是两个分块，所以另一个分块的牛一定不喜欢这个分块的牛，不然互相喜欢，就是一个强连通分块了)
2. 出度为0的强连通分块只有一个
   (如果出现两个出度为0的强连通分块，那这两个分块的牛不喜欢对方，那么就没有牛是明星)

Code

#include <iostream>
#include <cstdio>using namespace std;struct DT{int to, next;
}Ta[500000];
int n, m, dye, ans, Tnum, now, top, x, y, s[10100], times[10100];
int Ts[10100], Thead[10100], low[10100], dfn[10100], hep[10100], co[10100];void Tarjan(int x) {dfn[x] = low[x] = ++now;hep[++top] = x;for (int i = Thead[x]; i; i = Ta[i].next)if(!dfn[Ta[i].to]) {Tarjan(Ta[i].to);low[x] = min(low[x], low[Ta[i].to]);} else if (!co[Ta[i].to])low[x] = min(low[x], dfn[Ta[i].to]);if(dfn[x] == low[x]) {co[x] = ++dye;s[dye]++;  //统计分块中的牛while(hep[top] != x)co[hep[top--]] = dye, s[dye]++;--top; } 
}int main() {scanf("%d %d", &n, &m);for(int i = 1; i <= m; i++) {scanf("%d %d", &x, &y);Ta[++Tnum] = (DT){y, Thead[x]};Thead[x] = Tnum;}for(int i = 1; i <= n; i++)if (!dfn[i])Tarjan(i);for (int i = 1; i <= n; i++)for (int j = Thead[i]; j; j = Ta[j].next)if (co[i] != co[Ta[j].to])times[co[i]]++;  //统计出度for (int i = 1; i <= dye; i++)if(!times[i]) {  //1.明星在出度为0的强连通分块中if (!ans)  //2.出度为0的强连通分块只有一个ans = i;else ans = -1;  //如果有多个出度为0的强连通分块， 那么就没有牛是明星}if (ans == -1) printf("0");else printf("%d", s[ans]);  //出度为0的强连通分块中所有的牛都是明星
}