/*
强连通分量内的点可以互相传送,可以直接缩点
缩点后得到一棵树
第一问的答案是零入度点数量,
第二问: 加多少边后变成强连通图
树上入度为0的点有p个,出度为0的点为q,那么答案就是max(p,q)
如果缩点后是一个点,答案就是0
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define maxn 105
struct Edge{int to,nxt;}edge[<<];
int n,head[maxn],tot;
void addedge(int u,int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;
} int dfn[maxn],low[maxn],stack[maxn],ins[maxn],c[maxn],cnt,top,ind;
void tarjan(int x){
low[x]=dfn[x]=++ind;
stack[++top]=x;
ins[x]=;
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],low[y]);
}
if(dfn[x]==low[x]){
cnt++;
int y;
do{
y=stack[top--];
ins[y]=;
c[y]=cnt;
}while(y!=x);
}
}
void init(){
cnt=tot=ind=top=;
memset(dfn,,sizeof dfn);
memset(low,,sizeof low);
memset(stack,,sizeof stack);
memset(ins,,sizeof ins);
memset(c,,sizeof c);
memset(head,-,sizeof head);
}
int main(){
while(cin>>n){
init();
for(int i=;i<=n;i++){
int u=i,v;
while(scanf("%d",&v),v)
addedge(u,v);
}
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i);
if(cnt==){
printf("1\n0\n");
continue;
} //缩点
int in[maxn]={},out[maxn]={},p=,q=;
for(int x=;x<=n;x++)
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(c[x]==c[y])continue;
in[c[y]]++;out[c[x]]++;
}
for(int i=;i<=cnt;i++){
if(in[i]==)p++;
if(out[i]==)q++;
}
printf("%d\n%d\n",p,max(p,q));
}
}

最新文章

  1. Android N做了啥
  2. java日期处理SimpleDateFormat等
  3. sql查询指定范围内的所有月份
  4. 一篇旧文章,结合汇编探索this指针
  5. Repeater数据绑定和操作
  6. C# 程序自动批量生成 google maps 的KML文件
  7. 《高性能Javascript》读书笔记-2
  8. 手把手教小白如何用css+js实现页面中图片放大展示效果
  9. 模拟实现一个ATM+购物商城程序
  10. 统计表中 重复出现 XX次以上的数据
  11. Android实现自动更新功能
  12. VirtualBox 自动挂载共享文件夹
  13. dlo,学习清单
  14. 「2017 Multi-University Training Contest 1」2017多校训练1
  15. okhttp3与旧版本okhttp的区别分析
  16. [AHOI2009]维护序列
  17. Swift中关于集合计算的几种函数记录(intersect、symmetricDifference、union、subtract)
  18. android 开发 View _10_ Path之基本操作
  19. [转][CentOS]VI编辑器使用
  20. RxJS之catchError

热门文章

  1. 剑指Offer-表示数值的字符串
  2. Linux调试
  3. tcp黏包
  4. Linux C++ UDP Socket通信实例
  5. “指定的参数已超出有效值的范围”在【 parameterUpdate.Add(new OracleParameter(&quot;STATUS&quot;, 0));】报错
  6. 【VMware vSphere】使用U盘给戴尔服务器安装ESXi6.0系统
  7. nc替代技术方案
  8. Linux内存带宽的一些测试笔记【转】
  9. asyncio之asyncio.run
  10. 【转】vector中erase()的使用注意事项