1051: [HAOI2006]受欢迎的牛
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 8161 Solved: 4460
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
1
HINT
100%的数据N<=10000,M<=50000
题解：
这题一开始我用并查集乱搞了一下，结果搞出来了...
如果一头牛受欢迎，那么他所有喜欢的牛都是被所有牛认为受欢迎的。那么我们关键就是找出第一头被所有牛认为受欢迎的牛。
在合并集合的时候用sum数组维护喜欢父亲结点的个数，当个数等于n时我们就找到一头牛了。
之后再用个bfs来求就好了。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
using namespace std; const int N = ,M = ;
int n,m,tot;
int head[N],f[N],sum[N],vis[N];
map<int,map<int,int> > mp;
struct Edge{
int u,v,next ;
}e[M];
void adde(int u,int v){
e[++tot].u=u;e[tot].v=v;
e[tot].next=head[u];
head[u]=tot;
}
int find(int x){
return f[x]==x ? f[x] : f[x]=find(f[x]);
}
int main(){
cin>>n>>m;
int st=;
memset(head,-,sizeof(head));
for(int i=;i<=N-;i++) f[i]=i,sum[i]=;
for(int i=,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
if(!mp[u][v]){
mp[u][v]=;
adde(u,v);
int fx=find(u),fy=find(v);
if(fx!=fy){
f[fx]=fy;
sum[fy]+=sum[fx];
if(sum[fy]==n) st=fy;
}
}
}
int cnt =;
if(!st)puts("");
else{
queue<int> q;
q.push(st);vis[st]=;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].v;
if(!vis[v]){
vis[v]=;
q.push(v);
cnt++;
}
}
}
printf("%d\n",cnt);
}
return ;
}
再来说一下tarjan。
先用tarjan缩点，然后重新构图，找到出度为0的点那么这里面所有的牛都是被所有牛认为受欢迎的。
注意一下构图后不连通的情况就好了。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std; const int N = ,M = ;
int n,m,tot,num,T;
int head[N],dfn[N],low[N],vis[N],scc[N];
struct Edge{
int u,v,next ;
}e[M];
void adde(int u,int v){
e[++tot].u=u;e[tot].v=v;
e[tot].next=head[u];head[u]=tot ;
}
stack <int> s;
void Tanjan(int u){
dfn[u]=low[u]=++T;vis[u]=;
s.push(u);
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].v;
if(!vis[v]){
Tanjan(v);
low[u]=min(low[u],low[v]);
}else{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
num++;int now;
do{
now = s.top();s.pop();
scc[now]=num;
}while(!s.empty() && now!=u);
}
}
int main(){
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
for(int i=,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
adde(u,v);
}
for(int i=;i<=n;i++){
if(!vis[i]) Tanjan(i);
}
int out[N]={},in[N]={};
for(int u=;u<=n;u++){
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].v;
if(scc[u]!=scc[v]){
out[scc[u]]++;
in[scc[v]]++;
}
}
}
int cnt=,ans=,tag;
for(int i=;i<=num;i++) if(!out[i]) cnt++,tag=i;
if(cnt==){
for(int i=;i<=n;i++) if(scc[i]==tag) ans++;
printf("%d",ans);
}else puts("");
return ;
}