之前很多很多紫书上的东西我都忘了……

抄题解的后果……

做了一下裸题

https://vjudge.net/problem/UVA-10305

拓扑排序还可以来判环

#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std; const int MAXN = 1e3 + ;
struct Edge{ int to, next; };
Edge e[MAXN << ];
int head[MAXN], ans[MAXN], tot;
int vis[MAXN], n, m, t; void AddEdge(int from, int to)
{
e[tot] = Edge{to, head[from]};
head[from] = tot++;
} bool dfs(int u)
{
vis[u] = -;
for(int i = head[u]; ~i; i = e[i].next)
{
int v = e[i].to;
if(vis[v] == -) return false;
if(!vis[v] && !dfs(v)) return false;
}
vis[u] = ; ans[--t] = u;
return true;
} bool toopsort()
{
memset(vis, , sizeof(vis));
t = n + ;
_for(i, , n)
if(!vis[i] && !dfs(i))
return false;
return true;
} int main()
{
while(~scanf("%d%d", &n, &m) && n)
{
memset(head, -, sizeof(head)); tot = ;
_for(i, , m)
{
int u, v;
scanf("%d%d", &u, &v);
AddEdge(u, v);
} if(toopsort())
{
_for(i, , n - ) printf("%d ", ans[i]);
printf("%d\n", ans[n]);
}
else puts("NO");
} return ;
}

用bfs貌似更好写

#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std; const int MAXN = 1e3 + ;
struct Edge{ int to, next; };
Edge e[MAXN << ];
int head[MAXN], ans[MAXN], tot;
int d[MAXN], n, m, t, cnt; void AddEdge(int from, int to)
{
e[tot] = Edge{to, head[from]};
head[from] = tot++;
} bool toopsort()
{
queue<int> q;
_for(i, , n)
if(!d[i])
q.push(i);
while(!q.empty())
{
int u = q.front(); q.pop();
ans[++cnt] = u;
for(int i = head[u]; ~i; i = e[i].next)
{
int v = e[i].to;
d[v]--; if(!d[v]) q.push(v);
}
}
return cnt == n;
} int main()
{
while(~scanf("%d%d", &n, &m) && n)
{
memset(head, -, sizeof(head)); tot = ;
memset(d, , sizeof(d)); _for(i, , m)
{
int u, v;
scanf("%d%d", &u, &v);
AddEdge(u, v);
d[v]++;
} cnt = ;
if(toopsort())
{
_for(i, , n - ) printf("%d ", ans[i]);
printf("%d\n", ans[n]);
}
else puts("NO");
} return ;
}

最新文章

  1. PHP读取EXCEL时间
  2. JavaWeb---总结(十)JSP标签
  3. 《css3实战》读书笔记 第一章 基于CSS需求而编写的HTML.
  4. 【转】Basic C# OOP Concept
  5. 移动WebApp开发框架(珍藏)
  6. Java 中类与类之间的关系
  7. react中文API解读二(教程)
  8. AdaBoost的java实现
  9. iOS_20_微博OAuth授权_取得用户授权的accessToken
  10. C#开发短信发送
  11. JSX的替代方案(译文)
  12. java新知识系列 五
  13. java 自动拆箱
  14. centos7安装nginx1.10.1
  15. 二、Sql Server 基础培训《进度2-关于主键(知识点学习)》
  16. jQuery-2.DOM---节点插入
  17. body标签
  18. 1.编译cartographer ROS
  19. IIS配置过程中的常见问题
  20. C# 监控代码执行效率

热门文章

  1. js实现本地的图片压缩上传预览
  2. codevs——T2102 石子归并 2
  3. jqury+animation+setTimeOut实现渐变显示与隐藏动画
  4. 虚拟ONVIF 摄像机
  5. Android接口和框架学习
  6. sql不显示反复列
  7. Codeforces Round #272 (Div. 2) 题解
  8. 【Java集合源代码剖析】LinkedList源代码剖析
  9. poj2947Widget Factory
  10. PHPStorm中使用bootstrap3控件!