【强联通分量缩点】【Tarjan】bzoj1051 [HAOI2006]受欢迎的牛

时间:2021-05-17 00:09:05

就是看是否有一些点,从其他任何点出发都可到达

定理:有向无环图中唯一出度为0的点,一定可以由任何点出发均可达。

所以缩点,若出度为零的点(强联通分量)唯一,则答案为该强联通分量中点的度数。

若不唯一,答案为0,易证。

Code(懒得Tarjan,用了两次DFS):

 #include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<int>order;
int v[],first[],next[],en;
int a[],b[],scc[],num[],sum,chu[];
bool vis[];
int n,m;
inline void AddEdge(const int &U,const int &V){v[++en]=V;next[en]=first[U];first[U]=en;}
void Clear()
{
memset(v,,sizeof(v));
memset(first,,sizeof(first));
memset(next,,sizeof(next));
en=;
}
void dfs(int cur)
{
vis[cur]=true;
for(int i=first[cur];i;i=next[i])
if(!vis[v[i]])
dfs(v[i]);
order.push_back(cur);
}
void dfs2(int cur,int sum)
{
vis[cur]=true;
scc[cur]=sum;
num[sum]++;
for(int i=first[cur];i;i=next[i])
if(!vis[v[i]])
dfs2(v[i],sum);
}
void Scc()
{
for(int i=;i<=n;i++)
if(!vis[i])
dfs(i);
memset(vis,false,sizeof(vis));Clear();
for(int i=;i<=m;i++)AddEdge(b[i],a[i]);
int sz=order.size();
for(int i=sz-;i>=;i--)
if(!vis[order[i]])
dfs2(order[i],++sum);
}
int Exam()
{
int cnt=,Record;
for(int i=;i<=m;i++)
if(scc[a[i]]!=scc[b[i]])
chu[scc[a[i]]]++;
for(int i=;i<=sum;i++)
if(!chu[i])
{
cnt++;
Record=i;
if(cnt==)
return ;
}
return num[Record];
}
int res;char C;
inline int Get()
{
res=;C='*';
while(C<''||C>'')C=getchar();
while(C>=''&&C<=''){res=res*+(C-'');C=getchar();}
return res;
}
int main()
{
n=Get();m=Get();
for(int i=;i<=m;i++){a[i]=Get();b[i]=Get();AddEdge(a[i],b[i]);}
Scc();printf("%d\n",Exam());
return ;
}

【强联通分量缩点】【Tarjan】bzoj1051 [HAOI2006]受欢迎的牛的更多相关文章

  1. &lbrack;BZOJ1051&rsqb;&lbrack;HAOI2006&rsqb; 受欢迎的牛 tarjan求联通分量

    1051: [HAOI2006]受欢迎的牛 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 5687  Solved: 3016[Submit][Sta ...

  2. &lbrack;BZOJ1051&rsqb; &lbrack;HAOI2006&rsqb; 受欢迎的牛 &lpar;强联通分量&rpar;

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

  3. Tarjan求强联通分量&plus;缩点

    提到Tarjan算法就不得不提一提Tarjan这位老人家 Robert Tarjan,计算机科学家,以LCA.强连通分量等算法闻名.他拥有丰富的商业工作经验,1985年开始任教于普林斯顿大学.Tarj ...

  4. bzoj1051&colon; &lbrack;HAOI2006&rsqb;受欢迎的牛(强联通)

    1051: [HAOI2006]受欢迎的牛 题目:传送门 题解: 今天又做一道水题... 强联通啊很明显 水个模板之后统计一下每个强联通分量中点的个数,再统计一下出度... 不难发现:缩点之后当且仅当 ...

  5. bzoj1051 &lbrack;HAOI2006&rsqb;受欢迎的牛 tarjan&amp&semi;&amp&semi;缩点

    题目描述 每头奶牛都梦想成为牛棚里的明星.被所有奶牛喜欢的奶牛就是一头明星奶牛.所有奶 牛都是自恋狂,每头奶牛总是喜欢自己的.奶牛之间的“喜欢”是可以传递的——如果A喜 欢B,B喜欢C,那么A也喜欢C ...

  6. 【强联通分量缩点】【最长路】【spfa】CH Round &num;59 - OrzCC杯NOIP模拟赛day1 队爷的讲学计划

    10分算法:对于城市网络为一条单向链的数据, 20分算法:对于n<=20的数据,暴力搜出所有的可能路径. 结合以上可以得到30分. 60分算法:分析题意可得使者会带着去的城市也就是这个城市所在强 ...

  7. 【最小割】【Dinic】【强联通分量缩点】bzoj1797 &lbrack;Ahoi2009&rsqb;Mincut 最小割

    结论: 满足条件一:当一条边的起点和终点不在 残量网络的 一个强联通分量中.且满流. 满足条件二:当一条边的起点和终点分别在 S 和 T 的强联通分量中.且满流.. 网上题解很多的. #include ...

  8. bzoj1051&colon; &lbrack;HAOI2006&rsqb;受欢迎的牛(tarjan板子)

    1051: [HAOI2006]受欢迎的牛 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 6064  Solved: 3179[Submit][Sta ...

  9. &lbrack;Bzoj1051&rsqb;&lbrack;HAOI2006&rsqb;受欢迎的牛(缩环)

    1051: [HAOI2006]受欢迎的牛 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 6676  Solved: 3502[Submit][Sta ...

随机推荐

  1. Kafka副本管理—— 为何去掉replica&period;lag&period;max&period;messages参数

    今天查看Kafka 0.10.0的官方文档,发现了这样一句话:Configuration parameter replica.lag.max.messages was removed. Partiti ...

  2. mysql

    这是 <MySQL 必知必会> 的读书总结.也是自己整理的常用操作的参考手册. 使用 MySQL 连接到 MySQL shell>mysql -u root -p Enter pas ...

  3. c&num; 参数传递

    c#类型有值类型与引用类型. 无论哪种类型的变量,作为方法的参数进行传递时,默认是以"值传递"方式来传递的. 传递给方法的形参,在执行时都会新创建一个局部变量,然后接受实参的值, ...

  4. MYSQL 错误 :Out of resources when opening file &&num;39&semi;&period;&sol;datagather&sol;mx&lowbar;domain&num;P&num;p178&period;MYD&&num;39&semi; &lpar;Errcode&colon; 24&rpar; 解决办法

    出现Out of resources when opening file './xxx.MYD' (Errcode: 24)错误是因为打开的文件数超过了my.cnf的--open-files-limi ...

  5. 数据类型 varchar 和 uniqueidentifier 在 add 运算符中不兼容

    select '<a href="/'+a.id +'" title="'+ a.title +'">'+a.Title+'</a>' ...

  6. MySql与python交互

    No1: 引入MySql:python2是Mysqldb,python3是pymysql No2: Connection对象 用于建立与数据库的连接 创建对象:调用connect()方法 conn=c ...

  7. Vs自定nuget push菜单

    1.需要准备 nuget.exe 和 nuget-push.cmd 命名行 nuget.ext 下载地址:https://files.cnblogs.com/files/liuxiaoji/nuget ...

  8. Eclipse优化常用方法

    Eclipse优化常用方法如下: 1.减少不必要的验证 将Manual保持不动,build里面只留下classpath dependency Validator,其他的全部去掉.如果以后需要对文件进行 ...

  9. 使用python type动态创建类

    使用python type动态创建类 X = type('X', (object,), dict(a=1))  # 产生一个新的类型 X 和下列方法class X(object):    a = 1效 ...

  10. Eclipse Java注释模板设置简介&comma;更改字体大小

    为类添加注释:此为我的模板设置注释模板的入口: Window->Preference->Java->Code Style->Code Template 然后展开Comments ...