受欢迎的牛 [HAOI2006] [强连通] [传递闭包(划)]

Description

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

Input

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

Output

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

Sample Input

3 3

1 2

2 1

2 3

Sample Output

Hint

10%的数据N＜=20,M＜=50
30%的数据N＜=1000,M＜=20000
70%的数据N＜=5000,M＜=50000
100%的数据N＜=10000,M＜=50000

Solution

首先，如果数据很小的话可以用传递闭包对吧，但是N到了1e5就显然不行了。

显然如果在一个环里的各个点的传递是互达的，由此我们可以扩展到一个强连通分量也是这样。

于是我们就可以想到tarjan缩点。

缩完点后怎么办呢？愚蠢的我想到一个点的入度=点数-1就对答案产生贡献，显然是不对的（如 3->2->1）。

于是我第一遍只有70分，（这样都有70分可能是数据太水了）。

脑子不好使的我冒着被卡的风险在缩完点后使用传递闭包（不要问我为什么我这么喜欢传递闭包），居然过了！（可能是数据太水了）

然后我便看正解，发现果然还是大佬们聪明一点。

对于缩完点后的点x

i）如果出度！=0，那么肯定有没指向自己的点，（如果有指出去后又指回来肯定在连通分量内）

ii）如果出度==0，似乎这个连通分量内的点就是答案，但是如果有多个出度为0的点，就说明还有多个独立的区域，那也不行。

所以出度==0的点有且只有一个的时候即为答案

Code (传递闭包版）

 #include<set>

 #include<stack>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define RG register int

 #define rep(i,a,b)    for(RG i=a;i<=b;i++)

 #define per(i,a,b)    for(RG i=a;i>=b;i--)

 #define inf (1<<30)

 #define maxn 10005

 #define maxm 500005

 #define add(x,y) e[++cnt].u=u,e[cnt].v=v,e[cnt].next=head[u],head[u]=cnt

 using namespace std;

 stack<int> stk;

 set<int> st[maxn];

 int n,m,cnt,id,sid,ans;

 int head[maxn],scc[maxn],dfn[maxn],low[maxn],vis[maxn],ind[maxn],sz[maxn],oud[maxn];

 int gra[][];

 struct E{

     int u,v,next;

 }e[maxm];

 inline int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void tarjan(int u,int fa)

 {

     low[u]=dfn[u]=++id;

     stk.push(u);vis[u]=;

     for(int i=head[u];i;i=e[i].next)

     {

         int v=e[i].v;

         if(!dfn[v])

         {

             tarjan(v,u);low[u]=min(low[u],low[v]);

         }

         else if(vis[v])    low[u]=min(low[u],dfn[v]);

     }

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

     {

         ++sid;int x;

         do{

             x=stk.top(),stk.pop();

             vis[x]=,scc[x]=sid,sz[sid]++;

         }while(x!=u);

     }

 }

 int main()

 {

     n=read(),m=read();

     RG u,v;rep(i,,m) u=read(),v=read(),add(u,v);

     rep(i,,n)    if(!scc[i])    tarjan(i,);

     rep(i,,cnt)

     {

         int x=scc[e[i].u],y=scc[e[i].v];

         if(x!=y)

             gra[x][y]=;

     }

     rep(k,,sid)

         rep(i,,sid)

             rep(j,,sid)

                 if(gra[i][k]&&gra[k][j])gra[i][j]=;

     rep(i,,sid)

     {

         int flg=;

         rep(j,,sid)

             if(i!=j&&!gra[j][i]) flg=;

         if(!flg) ans+=sz[i];

     }

     cout<<ans;

     return ;

 }

>>点击查看代码<<

 #include<set>

 #include<stack>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define RG register int

 #define rep(i,a,b)    for(RG i=a;i<=b;i++)

 #define per(i,a,b)    for(RG i=a;i>=b;i--)

 #define inf (1<<30)

 #define maxn 10005

 #define maxm 500005

 #define add(x,y) e[++cnt].u=u,e[cnt].v=v,e[cnt].next=head[u],head[u]=cnt

 using namespace std;

 stack<int> stk;

 set<int> st[maxn];

 int n,m,cnt,ccnt,id,sid,ans;

 int head[maxn],hh[maxn],scc[maxn],dfn[maxn],low[maxn],vis[maxn],ind[maxn],sz[maxn],oud[maxn];

 int gra[][];

 struct E{

     int u,v,next;

 }e[maxm];

 struct EE{

     int v,next;

 }edge[maxm];

 inline int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void tarjan(int u,int fa)

 {

     low[u]=dfn[u]=++id;

     stk.push(u);vis[u]=;

     for(int i=head[u];i;i=e[i].next)

     {

         int v=e[i].v;

         if(!dfn[v])

         {

             tarjan(v,u);low[u]=min(low[u],low[v]);

         }

         else if(vis[v])    low[u]=min(low[u],dfn[v]);

     }

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

     {

         ++sid;int x;

         do{

             x=stk.top(),stk.pop();

             vis[x]=,scc[x]=sid,sz[sid]++;

         }while(x!=u);

     }

 }

 int main()

 {

     n=read(),m=read();

     RG u,v;rep(i,,m) u=read(),v=read(),add(u,v);

     rep(i,,n)    if(!scc[i])    tarjan(i,);

     rep(i,,cnt)

     {

         int x=scc[e[i].u],y=scc[e[i].v];

         if(x!=y)

             gra[x][y]=;

     }

     rep(k,,sid)

         rep(i,,sid)

             rep(j,,sid)

                 if(gra[i][k]&&gra[k][j])gra[i][j]=;

     rep(i,,sid)

     {

         int flg=;

         rep(j,,sid)

             if(i!=j&&!gra[j][i]) flg=;

         if(!flg) ans+=sz[i];

     }

     cout<<ans;

     return ;

巴特西