poj1236是问把一棵树变成强联通分量，于是答案就是rudu为0的和出度为0的最大值，因为假设入度为0的多一些，先每个出度为0的连接一个入度为0的，那么还剩一些入度为0的，这时候入度为0的随意连接一些出度为0的，都可以通过不停地绕绕绕绕成为一个强联通分量。
这题是把一个有向图变成强联通分量，先把他们缩点，变成很多棵树，然后再求入度为0，和出度为0的总点数那个多，虽然他们是很多棵树的入度点和出度点，但是是一样的，最后总能绕绕绕绕绕变成强联通分量，不需要去管他们是哪棵树上的。
#include<cstdio>
#include<cstring>
#define maxl 10010
#define maxm 100010
int n,m,top,ans,cnt,ff,num;
int rudu[maxl],out[maxl],f[maxl],dfn[maxl],low[maxl],s[maxl],ehead[maxl];
struct ed{int to,nxt;} e[maxm];
bool in[maxl];
void prework()
{
scanf("%d%d",&n,&m);
memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
memset(ehead,0,sizeof(ehead));
memset(rudu,0,sizeof(rudu));memset(out,0,sizeof(out));
int u,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
e[i].to=v;e[i].nxt=ehead[u];ehead[u]=i;
}
}
void tarjan(int u)
{
int v;s[++top]=u;in[u]=true;
dfn[u]=low[u]=++num;
for(int i=ehead[u];i;i=e[i].nxt)
{
v=e[i].to;
if(!dfn[v])
{
tarjan(v);
if(low[v]<low[u])
low[u]=low[v];
}
else
if(in[v] && dfn[v]<low[u])
low[u]=dfn[v];
}
if(dfn[u]==low[u])
{
ff++;
do
{
v=s[top];s[top]=0;top--;
f[v]=ff;
in[v]=false;
}while(v!=u);
}
}
inline int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
void mainwork()
{
memset(in,false,sizeof(in));
num=0;top=0;ff=0;
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
int v;
for(int u=1;u<=n;u++)
for(int i=ehead[u];i;i=e[i].nxt)
{
v=e[i].to;
if(f[u]!=f[v])
out[f[u]]++,rudu[f[v]]++;
}
int root=0,leaf=0;
for(int i=1;i<=ff;i++)
{
if(rudu[i]==0) root++;
if(out[i]==0) leaf++;
}
if(ff==1)
ans=0;
else
ans=max(root,leaf);
}
void print()
{
printf("%d\n",ans);
}
int main()
{
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
prework();
mainwork();
print();
}
return 0;
}
文章浏览阅读711次。adb（调试桥）：debug工具。adb作用：借助adb工具，可以管理设备或手机模拟器状态。adb相关操作命令如下： 1. 显示系统中全部Android平台： android list targets2. 显示系统中全部AVD（模拟器）： android list avd3. 创建AVD（模拟器）： android create avd_android的shell命令工具:设备规范管理
文章浏览阅读769次，点赞10次，收藏7次。Centos 7.9 在线安装 VirtualBox 7.0_centos安装virtualbox
文章浏览阅读7.3w次，点赞156次，收藏636次。下载和安装java，VsCode 快速配置 java环境，教程带图简单易懂。_vscode配置java开发环境
文章浏览阅读3.1k次，点赞4次，收藏29次。Ubuntu命令大全，方便使用_ubuntu可执行文件如何用命令执行
文章浏览阅读793次。问题:java.sql.SQLException: The server time zone value ‘�й���ʱ��’ is unrecognized or represents more than one time zone. You must configure either the server or JDBC driver (via the serverTimezone con..._eclipse连接mysql 出错java.sql.sqlexception: the server time zone value
本文介绍了C/C++数组的概念和特点，以及一维数组的定义方式。数组是存放相同类型数据元素的集合，具有相同数据类型和连续内存位置的特点。文章以代码示例的方式展示了一维数组的定义和使用。
文章浏览阅读2.8k次。2017-08-02@erixhao 技术极客TechBoosterAI 机器学习第二篇 - 非线形回归分析。我们上文深入本质了解了机器学习基础线性回归算法后，本文继续研究非线性回归。非线性回归在机器学习中并非热点，并且较为小众，且其应用范畴也不如其他广。鉴于此，我们本文也将较为简单的介绍，并不会深入展开。非线性回归之后，我们会继续经典机器学习算法包括决策_非线性回归分析方法
文章浏览阅读164次。一、关系运算：1.等值比较: =语法：A=B操作类型：所有基本类型描述:如果表达式A与表达式B相等，则为TRUE；否则为FALSE举例：hive>select 1 from lxw_dual where 1=1;12.不等值比较: <>语法: A <> B操作类型:所有基本类型描述:如果表达式A为NULL，或者表..._josn mincol
文章浏览阅读767次。1 FI/SD 借口配置FI/SD通过tcode VKOA为billing设置过帐科目，用户可以创建自己的科目定义数据表。 科目是做到COA级的，通过KOFI/KOFK这两个condition type确定分别过帐到FI和CO凭证中。 由于PricingProc.是同Sale_sd 和fi 接口产生什么凭证?
文章浏览阅读229次。转：http://blog.sae.sina.com.cn/archives/981按：这几天我一直在写这篇东西，本来是胸有成竹，没想到后来越写越发现自己在这个题目下有太多话想说，而以我现在的能力又不能很好地概括总结，以至于越写越长，文章结构也变得混乱，到后来修改的时候每次都要考虑好久才能下笔，所以决定拆成两部分来发，以便阅读。这篇写得我心力交瘁，质量不算好，凑合着看吧。同样是写程序..._研发和开发
文章浏览阅读1.6k次。1.关于进程守护无非就是6.0以下,6.0以上的高版本保活a.android中6.0以下的保护采用双线程守护即可是aidl (1)创建aidl文件 interface IServiceAidlInterface { String getServiceName(); } (2)创建本地service是LocalService类实现aid..._jobintentservice跨进程
文章浏览阅读657次。FastGithub：github加速神器，解决github打不开、用户头像无法加载、releases无法上传下载、git-clone、git-pull、git-push失败等问题。_fastgithub 程序将自动关闭:系统已运行其它实例