CodeForces CF875C題解

• 2021 年 4 月 6 日
• 筆記
• 題解

題解

非常有意思的\(2-SAT\)的題。

聽學長講完之後感覺確實容易想到\(2-SAT\)，順理成章。

顯然，對於兩個串，對咱們來說有意義的顯然是兩個串中第一個不同的數字。那麼，我們假設兩個串分別是\(A,B\)，第一個不同的位置是\(pos\)，且\(A_{pos}=x,B_{pos}=y\)，如果\(x>y\)，那麼顯然我們需要給\(x\)加一個\('\)，且\(y\)一定不能加，要不然沒有意義。所以我們把\(x+m\)向\(y\)連邊，反之就反著來就好了。

然後就可以跑一遍\(2-SAT\)，就像模板一樣，如果\(color_i==color_{i+m}\)，就可以直接輸出\(No\)。然後就統計答案即可。

程式碼

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int tot,head[N],ver[N<<1],nxt[N<<1],a[N],lst[N];
int n,m,lstlen;
int num,dfn[N],low[N];
int color[N],cnt,st[N],top,ans;
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<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
void add(int x,int y)
{
    tot++;
    ver[tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void Tarjan(int x)
{
    low[x]=dfn[x]=++num;
    st[++top]=x;
	for(int i=head[x];i;i=nxt[i])
    {
		int y=ver[i];
		if(!dfn[y]) Tarjan(y),low[x]=min(low[x],low[y]);
		else if(!color[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		int y=-1;
        cnt++;
		while(x!=y)
        {
			y=st[top--];
            color[y]=cnt;//cout<<y<<" "<<cnt<<endl;
		}
	}
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        int len=read();
        bool flag=false;
        for(int j=1;j<=len;j++) a[j]=read();
        for(int j=1;j<=min(lstlen,len);j++) 
        {
            if(a[j]==lst[j]) continue;
            flag=true;
            if(a[j]>lst[j]) add(a[j]+m,lst[j]+m),add(lst[j],a[j]);
            else add(lst[j],lst[j]+m),add(a[j]+m,a[j]);
            break;
        }
        if(!flag && lstlen>len) puts("No"),exit(0);
        lstlen=len;
        for(int j=1;j<=lstlen;j++) lst[j]=a[j];
    }

    for(int i=1;i<=(m<<1);i++) if(!dfn[i]) Tarjan(i);
    for(int i=1;i<=m;i++) if(color[i]==color[i+m]) puts("No"),exit(0);
    puts("Yes");
    for(int i=1;i<=m;i++) if(color[i+m]<color[i]) ans++;
    cout<<ans<<endl;
    for(int i=1;i<=m;i++) if(color[i+m]<color[i]) cout<<i<<" ";
    return 0;
}