#. 关系运算图（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);

}