https://www.luogu.org/problemnew/show/2002

Tarjan 缩点 + 入度判断

#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std;
const int N = 1e5 + ;
const int M = 5e5 + ; #define yxy getchar() int Tarjan_tim, now = , n, m, topp, bel;
int Stack[N], head[N], dfn[N], low[N], belong[N], Out[N];
struct Node {int u, v, nxt;} G[M];
bool vis[N]; inline int read(){
int x = ; char c = yxy;
while(c < '' || c > '') c = yxy;
while(c >= '' && c <= '') x = x * + c - '', c = yxy;
return x;
} inline void add(int u, int v){
G[now].u = u; G[now].v = v; G[now].nxt = head[u]; head[u] = now ++;
} void Tarjan(int u){
dfn[u] = low[u] = ++ Tarjan_tim;
vis[u] = ;
Stack[++ topp] = u;
for(int i = head[u]; ~ i; i = G[i].nxt){
int v = G[i].v;
if(!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(vis[v]) low[u] = min(low[u], low[v]);
}
if(dfn[u] == low[u]){
vis[u] = ; belong[u] = ++ bel;
while(Stack[topp] != u){
vis[Stack[topp]] = ;
belong[Stack[topp]] = bel;
topp --;
}
topp --;
}
} int main()
{
n = read(); m = read();
for(int i = ; i <= n; i ++) head[i] = -;
for(int i = ; i <= m; i ++) {
int u = read(); int v = read();
add(u, v);
}
for(int i = ; i <= n; i ++) if(!dfn[i]) Tarjan(i);
for(int u = ; u <= n; u ++){
for(int i = head[u]; ~ i; i = G[i].nxt){
int v = G[i].v;
if(belong[u] != belong[v]) Out[belong[v]] ++;
}
}
int Answer();
for(int i = ; i <= bel; i ++) if(!Out[i]) Answer ++;
cout << Answer;
return ;
}

最新文章

  1. 初尝Brnshop移植到Linux Mono Jexus环境运行
  2. Linux查看系统状态命令
  3. Web.config配置详解
  4. webpack构建与loaders
  5. C语言 homework(4)
  6. C#综合揭秘——细说多线程(上)
  7. 记录一些容易忘记的属性 -- NSTimer
  8. java基础回顾(四)——锁机制
  9. Codeforces Round #331 (Div. 2)C. Wilbur and Points 贪心
  10. office在线预览方案
  11. storm的功能、三大应用
  12. ERROR 1045 (28000): Access denied for user &#39;root&#39;@&#39;localhost&#39;
  13. CSS的权重(转)
  14. ASP.NET WebAPI HTTPS
  15. mysql 常用技巧
  16. 基于Windows服务的聊天程序(一)
  17. beta冲刺用户测评-咸鱼
  18. js检查身份证号是否正确
  19. 用 VSCode 编写 python
  20. eclipse导入项目时,仅项目名出现红叉

热门文章

  1. Centos 安装 graylog
  2. uboot 添加自定义命令
  3. uboot-的start.S详细注解及分析
  4. k8s系列0--Kubernetes基础知识
  5. (九) spring 使用自定义限定符注解
  6. nlopt 二次优化
  7. 基于【 Docker】三 || Docker的基本操作
  8. spring 实现事务配置的方式
  9. linux:# vi /etc/profile -bash: vi: command not found 的解决办法
  10. windows使用zip包安装mysql8.0.12