1051: [HAOI2006]受歡迎的牛

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?4573??Solved:?2428
[Submit][Status][Discuss]

Description

每一頭牛的愿望就是變成一頭最受歡迎的牛。現(xiàn)在有N頭牛，給你M對(duì)整數(shù)(A,B)，表示牛A認(rèn)為牛B受歡迎。 這 種關(guān)系是具有傳遞性的，如果A認(rèn)為B受歡迎，B認(rèn)為C受歡迎，那么牛A也認(rèn)為牛C受歡迎。你的任務(wù)是求出有多少頭 牛被所有的牛認(rèn)為是受歡迎的。

Input

第一行兩個(gè)數(shù)N,M。 接下來M行，每行兩個(gè)數(shù)A,B，意思是A認(rèn)為B是受歡迎的（給出的信息有可能重復(fù)，即有可 能出現(xiàn)多個(gè)A,B）

Output

　　一個(gè)數(shù)，即有多少頭牛被所有的牛認(rèn)為是受歡迎的。

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

HINT

?

100%的數(shù)據(jù)N<=10000,M<=50000

?

?

題目鏈接：BZOJ 1051

做法：Tarjan縮點(diǎn)后，由于縮點(diǎn)后必定是一個(gè)DAG或者叫有向無環(huán)圖，因此應(yīng)該至少存在一個(gè)出度為0的縮點(diǎn)和一個(gè)入度為0的縮點(diǎn)，這題就是要統(tǒng)計(jì)出度為0的分量個(gè)數(shù)

若統(tǒng)計(jì)的數(shù)量有為1個(gè)，則說明全在一個(gè)連通分量內(nèi)，即任意兩點(diǎn)互相可達(dá)，所有牛都是受歡迎的；若大于1，則說明至少一個(gè)連通分量中的牛的數(shù)量少于n-1即歡迎不能直接或間接地全部集中在至少一頭牛身上，就沒有牛受歡迎了

代碼：

#include <stdio.h> #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define CLR(arr,val) memset(arr,val,sizeof(arr)) #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) typedef pair<int,int> pii; typedef long long LL; const double PI=acos(-1.0); const int N=10010; const int M=50010;struct edge {int to;int pre; }; edge E[M]; int head[N],tot; int dfn[N],low[N],st[N],belong[N],ins[N],sc,ts,top,scnum[N]; int out[N];void init() {CLR(head,-1);CLR(low,0);CLR(dfn,-1);CLR(belong,0);CLR(ins,0);sc=ts=top=0;CLR(scnum,0);CLR(out,0); } inline void add(int s,int t) {E[tot].to=t;E[tot].pre=head[s];head[s]=tot++; } void Tarjan(int u) {dfn[u]=low[u]=++ts;ins[u]=1;st[top++]=u;int v;for (int i=head[u]; ~i; i=E[i].pre){v=E[i].to;if(dfn[v]==-1){Tarjan(v);if(low[v]<low[u])low[u]=low[v];}else if(ins[v]){if(dfn[v]<low[u])low[u]=dfn[v];}}if(dfn[u]==low[u]){++sc;do{v=st[--top];ins[v]=0;belong[v]=sc;++scnum[belong[v]];}while (u!=v);} } int main(void) {int n,m,a,b,i,j,u,v;while (~scanf("%d%d",&n,&m)){init();for (i=0; i<m; ++i){scanf("%d%d",&a,&b);add(a,b);}for (i=1; i<=n; ++i)if(dfn[i]==-1)Tarjan(i);for (u=1; u<=n; ++u){for (j=head[u]; ~j; j=E[j].pre){v=E[j].to;if(belong[v]==belong[u])continue;++out[belong[u]];}}int zero_out=0;int scindx=-1;for (i=1; i<=sc; ++i){if(!out[i]){++zero_out;scindx=i;}}zero_out>1?puts("0"):printf("%d\n",scnum[scindx]);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Blackops/p/5991811.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1051 受欢迎的牛（Tarjan缩点）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。