ac代码

#include <bits/stdc++.h>
using namespace std;
const int N=1005,M=N,NM=N*M;
int a[N][N];
int h[NM],e[NM],ne[NM],idx;
bool st[NM];
int cnt;
int d[NM];
vector<int>res;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void topsort()
{
    priority_queue<int>q;  //默认是大根堆，但是可以取相反数得小根堆  
    //因为如果有多个方块可以拿起时，选择编号较小的，每次队列里放的都是入度为0的方块，即可以拿起的方块
    for(int i=1;i<NM;i++){
        if(st[i]&&d[i]==0)    q.push(-i);
    }

    while(q.size())
    {
        int t=-q.top();
        res.push_back(t);
        q.pop();

        for(int i=h[t];~i;i=ne[i])
        {
            int son=e[i];
            if(--d[son]==0)    q.push(-son);
        }
    }
}

int main()
{
    memset(h,-1,sizeof h);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int s=a[i][j];
            if(!st[s])    st[s]=1,cnt++;   //统计有哪些节点编号和节点总数
            if(i+1<=n&&a[i+1][j]!=s){  //建图
                int t=a[i+1][j];
                add(s,t);
                d[t]++;  
                //不用担心两个节点中有多条边，因为增加边的同时入度也增加了
            }
        }
    }

    topsort();

    if(res.size()==cnt){
        for(int i=0;i<cnt;i++){
            cout<<res[i];
            if(i!=cnt-1)    cout<<' ';
        }
    }
    else{
        for(auto t:res){
            cout<<t<<' ';
        }
        cout<<"Impossible";
    }

    return 0;
}