传送门

分析

第一问我们不难想出是缩点之后的新图中入度为0的点的个数,对于第二问,我们画一画可以发现最优策略就是对于每一个入度为0的点都有一个出度为0的点连向它,而对于每一个出度为0的点也一定连向一个入度为0的点。所以最终答案即为出度为0的点和入度为0的点的最大值。注意特判缩点后只有一个点的情况。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
vector<int>v[];
int dfn[],low[],ist[],belong[],id[],od[],sum,cnt;
stack<int>a;
inline void tarjan(int x){
dfn[x]=low[x]=++cnt;
a.push(x);
ist[x]=;
for(int i=;i<v[x].size();i++)
if(!dfn[v[x][i]]){
tarjan(v[x][i]);
low[x]=min(low[x],low[v[x][i]]);
}else if(ist[v[x][i]]){
low[x]=min(low[x],dfn[v[x][i]]);
}
if(dfn[x]==low[x]){
sum++;
while(){
int u=a.top();
a.pop();
ist[u]=;
belong[u]=sum;
if(u==x)break;
}
}
return;
}
int main(){
int n,m,i,j,k,ans=,ans2=,tot=;
scanf("%d",&n);
for(i=;i<=n;i++){
scanf("%d",&m);
while(m){v[i].push_back(m);scanf("%d",&m);}
}
for(i=;i<=n;i++)
if(!dfn[i])tarjan(i);
for(i=;i<=n;i++)
for(j=;j<v[i].size();j++)
if(belong[i]!=belong[v[i][j]])
id[belong[v[i][j]]]++,od[belong[i]]++;
for(i=;i<=sum;i++){
if(!id[i])ans++;
if(!od[i])ans2++;
}
tot=max(ans,ans2);
if(sum==)tot=;
printf("%d\n%d\n",ans,tot);
return ;
}

最新文章

  1. WPF入门:XAML
  2. JS组件系列——图片切换特效:简易抽奖系统
  3. W3C代码标准规范
  4. 使用imap协议接收邮件
  5. C++ Primer 变量和基本类型
  6. Excel大数据量分段导入到Oracle
  7. php substr中文乱码最有效到解决办法 转:http://blog.sina.com.cn/s/blog_49b531af0100esah.html
  8. ARC指南2 - ARC的开启和禁止
  9. Hadoop Balance
  10. JSON反序列化实体类
  11. ( ̄y▽ ̄)~ 智能手机II
  12. linux 更换yum源
  13. 【Kafka源码】KafkaController启动过程
  14. Java笔记:语法基础
  15. python 爬取B站视频弹幕信息
  16. C#生成JOSN字符串
  17. 错误: Error creating bean with name &#39;studentController&#39;: Unsatisfied dependency expressed through field &#39;studentServiceImpl&#39;;
  18. python简明教程代码
  19. 从 Aliyun 经典网络迁移到 Aliyun VPC 网络
  20. Nginx配置笔记

热门文章

  1. 2.mysql优化---增删改优化
  2. JQuery 提供了两种方式来阻止事件冒泡。
  3. SQL夯实基础(三):聚合函数详解
  4. swing之checkbox
  5. Redis 分布式锁 - 分布式锁的正确实现方式
  6. hl7 V2中Message Control ID的含义及应用
  7. POJ3321(dfs序列+树状数组)
  8. Redis事务和watch
  9. Celery-4.1 用户指南: Application(应用)
  10. jvm调优(二)