传送门：

 

题意：有两个数组，一个数组有n个数，另一个数组有m个数。s[i][j]表示第一个数组第i个数和第二个数组第j个数的大小关系，要求构造出一种方案，使条件成立。

 

先考虑没有等于号的情况，那么就是裸的拓扑排序，现在多了一个等于号，就先进行并查集再拓扑就行了。

•注意点：1.在进行拓扑排序时一定要全部用father[x]作为节点

                2.一定要全部并查集做完以后再连边，否则可能刚连完father[x]就变了

1 #include
      
        2 using namespace std; 3 const int N=20001; 4 typedef pair
       
         pii; 5  6 int p[N],a[N]; 7 int n,m,judge=0; 8 int t[N],ans[N],b[N]; 9 char s[1020][1020];10 vector 
        
          v[2080];11 12 int f(int x)13 {14     if(p[x]==x) return x;15     return p[x]=f(p[x]);16 }17 18 void unite(int x,int y)19 {20     int xx=f(x),yy=f(y);21     p[yy]=p[xx];22 }23 24 int main()25 {26     memset(b,0,sizeof(b));27     memset(t,0,sizeof(t));28     scanf("%d %d",&n,&m);29     for(int i=1;i<=n+m;i++) p[i]=i;30     for(int i=1;i<=n;i++)31     {32         scanf("%s",s[i]+1);33         for(int j=1;j<=m;j++)34         {35             if(s[i][j]=='=') 36             {37                 unite(i,j+n);38             }39         }40     }41     for(int i=1;i<=n;i++)42     {43         for(int j=1;j<=m;j++)44         {45             if(s[i][j]=='>') v[f(j+n)].push_back(f(i)),t[f(i)]++;46             else if(s[i][j]=='<') v[f(i)].push_back(f(j+n)),t[f(j+n)]++;47         }48     }49     priority_queue
         
           q;50     for(int i=1;i<=n+m;i++) if(f(i)==i) judge++;51     for(int i=1;i<=n+m;i++)52     {53         if(!t[p[i]]&&!b[p[i]]) 54         {55             q.push(make_pair(p[i],1));56             b[p[i]]=1;57         }58     }59     int sum=0,num=1;60     while(!q.empty())61     {62         int now=q.top().first,w=q.top().second;63         q.pop(); sum++;64         ans[now]=w;65         for(int i=0;i