CF1131D tarjan，拓扑

题目链接

541div2
http://codeforces.com/contest/1131/problem/D

思路

给出n序列和m序列的相对大小关系
构造出最大值最小的序列
缩点+拓扑
小的向大的连边
相等的连个环
tarjan缩点，判断环内是否ok
最后拓扑
更新要这样

ans[v]=max(ans[v],ans[u]+1);

就是说取最后更新的一个，保证大小关系

代码

#include <bits/stdc++.h>
#define ll long long
#define iter vector<int>::iterator
using namespace std;
const int N=2007;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int M[N][N];
int n,m;
struct node {
    int v,nxt;
}e[N*N];
int head[N*N],tot;
void add(int u,int v) {
    // cout<<u<<" "<<v<<"\n";
    e[++tot].v=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
vector<int> G[N],col[N];
char s[N];
int dfn[N],low[N],stak[N],top,vis[N],cnt,js,belong[N],rt[N];
int ans[N],ru[N];
void tarjan(int u) {
     dfn[u]=low[u]=++cnt;
    vis[u]=1;
    stak[++top]=u;
    for(iter v=G[u].begin();v!=G[u].end();++v) {
        if(!dfn[*v]) {
            tarjan(*v);
            dfn[u]=min(dfn[u],dfn[*v]);
        } else 
        if(vis[*v])
            dfn[u]=min(dfn[u],low[*v]);
    }
    if(low[u]==dfn[u]) {
        ++js;
        while(stak[top]!=u) {
            vis[stak[top]]=0;
            col[js].push_back(stak[top]);
            belong[stak[top]]=js;
            top--;
        }
        top--;
        belong[u]=js;
        vis[u]=0;
        col[js].push_back(u);
    }
}
queue<int> q;
int main() {
    n=read(),m=read();
    for(int i=1;i<=n;++i) {
        scanf("%s",s+1);
        for(int j=1;j<=m;++j) {
            if(s[j]=='>') {
                M[j+n][i]=1;
                M[i][j+n]=-1;
                G[j+n].push_back(i);
                // cout<<j+n<<" "<<i<<"\n";
            }
            if(s[j]=='<') {
                M[i][j+n]=1;
                M[j+n][i]=-1;
                G[i].push_back(j+n);
                // cout<<i<<" "<<j+n<<"\n";
            }
            if(s[j]=='=') {
                G[j+n].push_back(i);
                G[i].push_back(j+n);
            // cout<<j+n<<" "<<i<<"\n";cout<<i<<" "<<j+n<<"?\n";
            }
        }
    }
    // for(int i=1;i<=n+m;++i) {
    //  for(int j=1;j<=n+m;++j) {
    //      cout<<M[i][j]<<" ";
    //  }
    //  puts("");
    // }
    for(int i=1;i<=m+n;++i)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=js;++i) {
        // cout<<col[i].size()<<"!\n";
        for(iter a=col[i].begin();a!=col[i].end();++a) {
            for(iter b=col[i].begin();b!=col[i].end();++b) {
                // cout<<*a<<" "<<*b<<" ?\n";
                if(M[*a][*b]!=0) {
                    // cout<<*a<<" "<<*b<<"\n";
                    cout<<"No";
                    return 0;
                }
            }
            // cout<<*a<<" ";
        }
        // puts("");
    }
    // return 0;
    for(int i=1;i<=n+m;++i) {
        for(int j=1;j<=n+m;++j) {
            if(M[i][j]==1) 
            if(belong[i]!=belong[j]) {
                add(belong[i],belong[j]);
//              cout<<belong[i]<<" "<<belong[j]<<"!!\n";
                ru[belong[j]]++;
            }
        }
    }
//  memset(ans,0x3f,sizeof(ans));
    for(int i=1;i<=js;++i) if(!ru[i]) q.push(i),ans[i]=1;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            ans[v]=max(ans[v],ans[u]+1);
            ru[v]--;
            if(!ru[v]) q.push(v);
        }
    }
//  for(int i=1;i<=js;++i) cout<<ans[i]<<" ";cout<<"\n";return 0;
    puts("Yes");
    for(int i=1;i<=n;++i) printf("%d ",ans[belong[i]]);
    puts("");
    for(int i=1;i<=m;++i) printf("%d ",ans[belong[i+n]]);
    return 0;
}
/*
3 3
<<<
<<=
<<=
*/