noip复习之拓扑排序
2024-09-08 13:27:31
之前很多很多紫书上的东西我都忘了……
抄题解的后果……
做了一下裸题
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 ;
}
最新文章
- PHP读取EXCEL时间
- JavaWeb---总结(十)JSP标签
- 《css3实战》读书笔记 第一章 基于CSS需求而编写的HTML.
- 【转】Basic C# OOP Concept
- 移动WebApp开发框架(珍藏)
- Java 中类与类之间的关系
- react中文API解读二(教程)
- AdaBoost的java实现
- iOS_20_微博OAuth授权_取得用户授权的accessToken
- C#开发短信发送
- JSX的替代方案(译文)
- java新知识系列 五
- java 自动拆箱
- centos7安装nginx1.10.1
- 二、Sql Server 基础培训《进度2-关于主键(知识点学习)》
- jQuery-2.DOM---节点插入
- body标签
- 1.编译cartographer ROS
- IIS配置过程中的常见问题
- C# 监控代码执行效率