其实这道题蛮水的

思路:

根据题意,他说有环,自然想到要用tarjan,后面就很简单了;

缩完点之后重新建图,开一个inin数组表示该点的入度是多少(psps:该点表示缩完点之后的大点);

最后统计一下那个点没有入度就好了;

下面是本蒟蒻的cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
#define maxn 10101110
stack<int>q;
struct Node
{
int next,to;
}e[maxn],ee[maxn];
int dfn[maxn],low[maxn],be[maxn];
int vis[maxn],in[maxn],headd[maxn];
int n,m,num,num1,ans,head[maxn];
//num1表示大点的个数,num表示tarjan中的编号
//head原图,e->原图;ee->新图 headd->新图
void add(int x,int y)
{
e[++head[]].next=head[x];
e[head[]].to=y;
head[x]=head[];
}
void ad(int x,int y)
{
ee[++headd[]].next=headd[x];
ee[headd[]].to=y;
headd[x]=headd[];
}
//这里我用的head[0],headd[0]表示是为了节省一个小小的空间
void tarjan(int x)
{
vis[x]=;q.push(x);
dfn[x]=low[x]=++num;
for(int i=head[x];i;i=e[i].next)
{
int t=e[i].to;
if(!dfn[t])
{
tarjan(t);
low[x]=min(low[x],low[t]);
}
else if(vis[t])
low[x]=min(low[t],low[x]);
}
if(dfn[x]==low[x])
{
vis[x]=;
be[x]=++num1;
while(q.top()!=x)
{
be[q.top()]=num1;
vis[q.top()]=;
q.pop();
}
be[q.top()]=num1;
vis[q.top()]=;
q.pop();
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int y,u;
scanf("%d%d",&y,&u);
add(y,u);
}//加边
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=;i<=n;i++)
for(int j=head[i];j;j=e[j].next)
if(be[i]!=be[e[j].to])
{
ad(be[i],be[e[j].to]);
in[be[e[j].to]]++;
//加新边同时记in
}
for(int i=;i<=num1;i++)
if(!in[i])
ans++;
printf("%d",ans);
return ;
}

最新文章

  1. formValidator 表单验证
  2. Jquery获取select 控件的change事件时选中的值
  3. [Git] 快速签出与更新所有远程分支.md
  4. MyEclipse代码提示快捷键和常用设置
  5. lintcode:移动零
  6. 重构9-Extract Interface(提取接口)
  7. Linux下设置静态IP和获取动态IP的方法
  8. js封装的类似java StringBuilder类
  9. shell脚本—根据文件个数定时备份
  10. Ubuntu 下 libgps 库的使用
  11. bzoj 4824: [Cqoi2017]老C的键盘
  12. [机器学习]模型评价参数,准确率,召回率,F1-score
  13. c# 上传图片到一个外链相册服务器
  14. LeetCode——162. Find Peak Element
  15. MOT北京站 | 卓越研发之路:亿万级云端架构演进
  16. 为什么 APM 能提升 IT 团队工作质量?
  17. java 多线程并发 synchronized 同步机制及方式
  18. 从零自学Java-6.使用循环重复执行操作
  19. OpenAI Gym
  20. Win7 安装 MongoDB

热门文章

  1. linux上限值网速、限值带宽
  2. DNS缓存中毒的知识
  3. mean shift 图像分割(一、二、三)
  4. sqlalchemy多对多查询
  5. Examples of Scikit-learn Usages
  6. eclipse在注释时候字体变成繁体字
  7. 09:vuex组件间通信
  8. Linux普通用户使用sudo免输密码(Debian/Redhat通用)
  9. centOS 7 gitlab安装
  10. jQuery 表单内容的获取