[Tarjan] Codeforces 949C. Data Center Maintenance

我们是要选一些 \(+1\) ,另一些不变。容易往 \(2-sat\) 方面想,考虑一个限制 \(a_x \neq a_y\) ,若 \(a_x+1 \equiv a_y\) 则若 \(x\) 选了,\(y\) 必选。若 \(a_y+1 \equiv a_x\) 则若 \(y\) 选了,\(x\) 必选。

然后发现这其实没有对称性 ,是比 \(2-sat\) 更简单的东西,就是一些依赖关系而已,然后就刷 \(Tarjan\) ,找没有后继的最小连通分量即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005,maxe=200005;
int n,m,P,a[maxn],color[maxn],fir[maxn],nxt[maxe],son[maxe],tot;
int v[maxn];
vector<int> ans;
void add(int x,int y){
//printf("%d -> %d\n",x,y);
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int dfn[maxn],low[maxn],Tim,blg[maxn],d[maxn],instk[maxn],stk[maxn],top,G;
vector<int> V[maxn];
void Tarjan(int x){
dfn[x]=low[x]=++Tim; stk[++top]=x; instk[x]=true;
for(int j=fir[x];j;j=nxt[j])
if(!dfn[son[j]]) Tarjan(son[j]), low[x]=min(low[x],low[son[j]]);
else if(instk[son[j]]) low[x]=min(low[x],dfn[son[j]]);
if(dfn[x]==low[x]){
G++;
do{
V[G].push_back(stk[top]); blg[stk[top]]=G;
instk[stk[top]]=false;
}while(stk[top--]!=x);
}
}
int main(){
freopen("cf949C.in","r",stdin);
freopen("cf949C.out","w",stdout);
scanf("%d%d%d",&n,&m,&P);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
int x,y; scanf("%d%d",&x,&y);
if((a[x]+1)%P==a[y]) add(x,y);
if((a[y]+1)%P==a[x]) add(y,x);
}
for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);
for(int i=1;i<=n;i++)
for(int j=fir[i];j;j=nxt[j]) if(blg[i]!=blg[son[j]]) d[blg[i]]++;
int k=1; for(int i=2;i<=G;i++) if(!d[i]&&V[k].size()>V[i].size()) k=i;
printf("%d\n",V[k].size());
for(int i=0;i<V[k].size();i++) printf("%d ",V[k][i]);
return 0;
}