POJ 2186 Popular Cows （Trajan缩点）

图论好难啊 搞了好久终于把这题a了
一开始题目看错了 以为并查集就能做
后来发现要求被其他所有牛喜欢的牛的数量
看了题解才知道要咋做 菜鸡落泪

题目思路

首先将牛之间的崇拜看作一个单向边
建图后用Trajan算法找强连通分量
因为每个强连通分量是能相互到达的 分量外的牛只要喜欢其中的一个
就一定会喜欢其他所有的牛
所以可以把每个强连通分量看作一个点 即缩点
然后在缩点后的图上 找出度为0的点
（只可能有一个出度为0的点 可自行证明）
这个点代表的强连通分量就是答案
不会Trajan算法的话可以看下面链接的视频讲的非常详细
https://www.bilibili.com/video/BV19J411J7AZ?from=search&seid=13131781039614019257

ac代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 1e4+10;
const int inf = 0x3f3f3f3f;
const ll llinf =0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;int a[maxn*5],b[maxn*5];
int first[maxn],len;
//下面数组从左到右分别记录属于的强连通分量，入栈序号，可回溯的最小序号，是否进栈，栈内元素，强连通分量中点的个数
int belong[maxn],dfn[maxn],low[maxn],ins[maxn],st[maxn],sz[maxn];
//下面数组记录的是缩点后每个强联通分量的出度
int out[maxn];
int tp,block,id;
struct node
{int to,next;
}e[maxn*5];void add(int u,int v)
{e[len].to=v;e[len].next=first[u];first[u]=len++;
}void init()
{id=tp=block=0;ms(dfn,0);ms(low,0);ms(sz,0);ms(out,0);ms(first,-1);
}void trajan(int u)
{dfn[u]=low[u]=++id;ins[u]=1;st[++tp]=u;for(int i=first[u];i!=-1;i=e[i].next){int v=e[i].to;if(!dfn[v]){trajan(v);low[u]=min(low[u],low[v]);}else if(ins[v]);{low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){block++;int v;do{v=st[tp--];ins[v]=0;belong[v]=block;sz[block]++;}while(u!=v);}
}int main()
{int n,m;len=0;init();scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&a[i],&b[i]);add(a[i],b[i]);}for(int i=1;i<=n;i++)if(!dfn[i])trajan(i);for(int i=1;i<=m;i++){int u=a[i],v=b[i];if(belong[u]!=belong[v])out[belong[u]]++;}int ans=0;int counts=0;for(int i=1;i<=block;i++){if(out[i]==0){ans=sz[i];counts++;}}if(counts==1)printf("%d\n",ans);elseprintf("0\n");}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！