今天讲了topological sort
问题：
判环：记录入队的点数，若<n则有环，可证；
算法：o（n）：queue or stack，而不是o（n^2）枚举
#. 关系运算图（vijos1094）
描述
提交
自定义测试
题目描述
给出一有向图，图中每条边都被标上了关系运算符‘<’,‘>’,‘=’。现在要给图中每个顶点标上一个大
于等于0小于等于k的某个整数使所有边上的符号得到满足。若存在这样的k，则求最小的k，
若任何k都无法满足则输出NO。 例如下表中最小的k为2。
结点1>结点2
结点2>结点3
结点2>结点4
结点3=结点4
如果存在这样的k，输出最小的k值；否则输出‘NO’。
输入格式
共二行，第一行有二个空格隔开的整数n和m。n表示图的结点个数，m表示图的边数，
其中1<=n<=, <=m<=。全部结点用1到n标出，图中任何二点之间最多只有一条边，
且不存在自环。 第二行共有3m个用空格隔开的整数，第3i-2和第3i-（<=i<=m）
个数表示第i条边的顶点。第3i个数表示第i条边上的符号，其值用集合{-，，}中的数表示：
-1表示‘<’, 表示‘=’, 1表示‘>’
输出格式
仅一行，如无解则输出‘NO’；否则输出最小的k的值。
输入样例
- - -
输出样例
限制与约定
时间限制：1s
空间限制：128MB
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=1e3+;
const int maxm=1e4+;
inline int read()
{
int a=;bool b=;char x=getchar();
while(x<''||''<x){
if(x='-')b=;
x=getchar();
}
while(''<=x&&x<=''){
a=(a<<)+(a<<)+x-'';
x=getchar();
}
return b ? a : -a ;
}
int f[maxn];
inline int find(int x){
if(f[x]==x)return x;
else return f[x]=find(f[x]);
}
int first[maxn],next[maxm],to[maxm],edge_count;
inline void add(int x,int y){
edge_count++;
to[edge_count]=y;
next[edge_count]=first[x];
first[x]=edge_count;
}
int Ans,ans[maxn],n,m,cnt,indegree[maxn],queue[maxn];
inline void topological_sort()
{
int rear=,front=;
for(int i=;i<=n;i++){
if(find(i)==i && !indegree[i]){
queue[front++]=i;
}
}
while(rear<front){
int pos=queue[rear];
for(int i=first[pos];i;i=next[i]){
int v=to[i];
indegree[v]--;
if(!indegree[v]){
queue[front++]=v;
ans[v]=ans[pos]+;
Ans=max(Ans,ans[v]);
}
}
rear++;
}
if(front<cnt){
printf("NO\n");
exit();
}
}
int u[maxm],v[maxm],b[maxm];
int main()
{
cnt=n=read();m=read();
for(int i=;i<=n;i++)f[i]=i;
for(int i=;i<=m;i++){ u[i]=read();v[i]=read();b[i]=read(); if(!b[i]){
int ru=find(u[i]);int rv=find(v[i]);
f[ru]=rv;
cnt--;
}
}
for(int i=;i<=m;i++){
int ru=find(u[i]);int rv=find(v[i]);
if(b[i]==){//以 小<于 为边
add(rv,ru);
indegree[ru]++;
}
else if(b[i]==-){
add(ru,rv);
indegree[rv]++;
}
}
topological_sort(); printf("%d",Ans);
}