正題

題目鏈接:https://www.luogu.com.cn/problem/P5782

---

題目大意

$n$對(duì)人，每對(duì)之間恰好有一個(gè)人出席。$m$對(duì)仇恨關(guān)系表示兩個(gè)人不能同時(shí)出席。

求是否有解并輸出。

$1\le n\le 8000,1\le m\le 20000$

---

解題思路

裸的$\text{2-SAT}$。AJ的任務(wù)罷了。

時(shí)間復(fù)雜度$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> using namespace std; const int N=3e5+10; struct node{int to,next; }a[N<<2]; int n,m,tot,cnt,num,ls[N],dfn[N],low[N],col[N]; bool ins[N];stack<int> s; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void tarjan(int x){dfn[x]=low[x]=++cnt;s.push(x);ins[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(ins[y])low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){++num;while(s.top()!=x){ins[s.top()]=0;col[s.top()]=num;s.pop();}col[x]=num;ins[x]=0;s.pop();}return; } int main() {scanf("%d%d",&n,&m);n*=2;for(int i=1;i<=n;i+=2)addl(i+n,i+1),addl(i+1+n,i),addl(i+1,i+n),addl(i,i+1+n);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y+n);addl(y,x+n);}for(int i=1;i<=2*n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=n;i++)if(col[i]==col[i+n])return puts("NIE")&0;for(int i=1;i<=n;i++)if(col[i]<col[i+n])printf("%d\n",i);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的P5782-[POI2001]和平委员会【2-SAT】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。