BZOJ 1051 受欢迎的牛

Description

每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。

Input

第一行两个数N,M。接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B）

Output

一个数，即有多少头牛被所有的牛认为是受欢迎的。

Sample Input

3 3
1 2
2 1
2 3

Sample Output

HINT

100%的数据N<=10000,M<=50000

Source

很明显，tarjan缩点+topsort，然后bitset大法好。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<bitset>

 #include<queue>

 #include<stack>

 #include<cstdlib>

 using namespace std;

 #define maxn 10010

 #define maxm 60010

 int n,m,cnt,tot,dfn[maxn],low[maxn],id[maxn],d[maxn];

 int side[maxn],toit[maxm],next[maxm];

 int nside[maxn],ntoit[maxm],nnext[maxm];

 stack <int> S; bitset <maxn> bit[maxn]; bool vis[maxn];

 inline void add(int a,int b) { next[++cnt] = side[a]; side[a] = cnt; toit[cnt] = b; }

 inline void ins(int a,int b)

 {

     nnext[++cnt] = nside[a]; ++d[b];

     nside[a] = cnt; ntoit[cnt] = b;

 }

 inline void dfs(int now)

 {

     S.push(now); dfn[now] = low[now] = ++cnt;

     for (int i = side[now];i;i = next[i])

         if (!vis[toit[i]])

         {

             if (!dfn[toit[i]]) dfs(toit[i]);

             low[now] = min(low[toit[i]],low[now]);

         }

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

     {

         ++tot;

         while (S.top() != now) vis[S.top()] = true,id[S.top()] = tot,S.pop();

         vis[S.top()] = true,id[S.top()] = tot,S.pop();

     }

 }

 inline void rebuild()

 {

     cnt = ;

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

     {

         bit[id[i]].set(i-);

         for (int j = side[i];j;j = next[j])

             if (id[i] != id[toit[j]]) ins(id[i],id[toit[j]]);

     }

 }

 inline void topsort()

 {

     queue <int> team;

     for (int i = ;i <= tot;++i) if (!d[i]) team.push(i);

     while (!team.empty())

     {

         int now = team.front(); team.pop();

         for (int i = nside[now];i;i = nnext[i])

         {

             bit[ntoit[i]] |= bit[now];

             if (!--d[ntoit[i]]) team.push(ntoit[i]);

         }

     }

     int ans = ;

     for (int i = ;i <= n;++i) if (bit[id[i]].count() == n) ++ans;

     printf("%d",ans);

 }

 int main()

 {

     freopen("1051.in","r",stdin);

     freopen("1051.out","w",stdout);

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

     for (int i = ;i <= n;++i) add(i,i);

     while (m--) { int a,b; scanf("%d %d",&a,&b); add(a,b); }

     cnt = ;

     for (int i = ;i <= n;++i) if (!dfn[i]) dfs(i);

     rebuild();

     topsort();

     fclose(stdin); fclose(stdout);

     return ;

 }

巴特西