题解 | dfs做法

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int mod=998244353;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),c=getchar();}
    return x*f;
}

const int N=2010;
int a[N][N],vis[N];
vector<int>adj[N];
vector<int>tmp;

bool dfs(int x)
{
    if(vis[x^1])return false;
    if(vis[x])return true;
    vis[x]=1;
    tmp.push_back(x);
    for(int i=0;i<adj[x].size();i++)
    {
        int to=adj[x][i];
        if(!dfs(to))return false;
    }
    return true;
}

void solve()
{
    int n=read(),m=read();
    for(int i=0;i<n;i++)for(int j=1;j<=m;j++)a[i][j]=read();
    for(int j=1;j<=m;j++)
    {
        vector<pii>co;
        for(int i=0;i<n;i++)
        {
            co.push_back({a[i][j],2*i});
            co.push_back({a[i][m-j+1],2*i+1});
        }

        sort(co.begin(),co.end());
        for(int i=0;i<co.size();)
        {
            int now=i;
            while(now<co.size()&&co[now].first==co[i].first)now++;
            //[i,now)颜色相同
            for(int u=i;u<=now-1;u++)
            {
                for(int v=u+1;v<=now-1;v++)
                {
                    if((co[u].second^co[v].second)==1)continue;
                    //不能共存只能分开连边
                    adj[co[u].second].push_back(co[v].second^1);
                    adj[co[v].second].push_back(co[u].second^1);
                }
            }
            i=now;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(vis[2*i]||vis[2*i+1])continue;
        tmp.clear();
        if(dfs(2*i))continue;
        else
        {
            for(int i=0;i<tmp.size();i++)vis[tmp[i]]=0;
            tmp.clear();
            if(dfs(2*i+1))continue;
            else
            {
                cout<<"No\n";
                return;
            }
        }
    }
    cout<<"Yes\n";
    vector<int>ans;
    for(int i=0;i<n;i++)if(vis[i*2+1])ans.push_back(i+1);
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
}

signed main()
{
    int T=1;
    while(T--)solve();
    return 0;
}