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;
}
文章浏览阅读826次，点赞2次，收藏9次。SRC挖掘-拿下CNVD证书开源&闭源&售卖系统_ihsdus.cn
文章浏览阅读9.9k次，点赞4次，收藏44次。1.评论框及评论内容展示模板如下： div id="comment"> h3>strong>发表评论:strong>h3> p>span>标题：span> input type="text" name="" id="comm_title" class="text">p> p>span>内容：span>textarea rows="10"_在页面中输入你的评论,单击“评论”按钮,如果留言区没有评论,则直接添加评论,如果
文章浏览阅读1.2k次。一 什么是mitmproxy 抓包工具2 mitmproxy抓包工具介绍pip install mitmproxy检测是否安装成功mitmproxy --version默认监听 8080端口,使用 -p 指定端口3 下载证书linux 中操作mitmproxytab 切换显..._mitm框架
文章浏览阅读1.7k次。一般情况使用c:out和el表达式的效果是一样的，如： hello(使用标签):hello(使用el表达式):${hello}那一般什么时候会使用c:out标签呢？有两种情况： (1)使用缺省值。有的时候某个东西没设值，但要输出缺省值，如果用el表达式什么都不输出，但可以使用c:out输出想要输出的缺省值；如下： hello(default="123"):这样就输出了想要输出的_jstl c:out输出有小数点
文章浏览阅读261次。问题项目中数据库表对应实体类中包含Date类型的数据，保存Date类型数据时，传入的参数是new Date()(获取当前时间)，但是在保存操作成功以后，在数据库中查看发现实际保存的时间比当前时间快解决最后发现是连接数据库的url中的时区参数是serverTimezone=UTC，把时区改成serverTimezone=GMT%2b8，问题解决..._jpa mysql 时间大小比较
文章浏览阅读103次。为什么80%的码农都做不了架构师？>>> ..._hotspot lir
文章浏览阅读172次。现在很多一键化的root工具，但是仍然有不少的三星手机是无法用全自动方式进行root的，这时候，我们可以选择使用手工的方式进行root，本文章对手工root的一些方法进行一些介绍。 常规方法：..._三星手机用面具root
文章浏览阅读1.7k次。原标题：2021年高三佛山一模，看佛山高中排名2021年1月11日佛山进行了新高考改革后第一次佛山一模考试，作为高考风向标，各高中的成绩具有很大参考意义。结合2018年中考录取分数、2021年佛山一模、2020年佛山一模对佛山56所高中进行简要分析，从而展望2021年高考。 1-10名石门中学稳居第一，佛山一中重夺第二，南海中学增长强劲，顺德一中略显颓势，李兆基中学增长强劲，郑裕彤中学加工能..._佛山国华纪念中学2021年高考成绩
文章浏览阅读1k次。---------查询公司pkselect pk_corp from bd_corp where unitcode='公司编码' 进行删除应收应付模块启用功能 删除2008与2006的行即可（删除行前，要删除期初录入的数据。） select * from sm_createcorp where pk_corp='1025' for update 解锁，删除行，点对勾，然后提前端f10_应付管理系统怎么清除数据
文章浏览阅读669次，点赞13次，收藏8次。嵌入式固件加密的几种方式_固件加密
文章浏览阅读1.2k次。1.Manifest文件中申请读写外部的权限<uses-permission android:name="android.permission.READ_EXTERNAL_STORAGE"/<uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE"/>2.高版本的需要动态申请权限int checkReadExternalPermission = checkSelfPermission(_不root 通讯录 存放目录
文章浏览阅读502次。)创建成功之后在表中添加信息：项目创建完毕的初始目录：初始pom.xml文件：4.创建核心配置文件(mybatis-condig.xml)4.1 准备数据库配置文件（db.properties）4.2 配置mybatis-condig.xml5.建包这里需要注意：在resources资源包下创建的是directory，创建方式为：实体类的属性要和数据库里面表的字段相对应，数据类型采用包装类。7.创建Xxxmapper接口（mapper）接口中定义对数据库进行操作的方法：8_使用mybatis的开发步骤