之前很多很多紫书上的东西我都忘了……
抄题解的后果……
做了一下裸题
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 ;
}