http://acm.hdu.edu.cn/showproblem.php?pid=1814
題意：n個2人組，編號分別為2n和2n+1，每個組選一個人出來，且給出m條關(guān)系（x,y）使得選了x就不能選y，問是否能從每個組選出1人。且輸出字典序最小的答案。（n<=8000, m<=20000）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N=8005, M=20005;
struct E { int next, to; }e[M<<1];
int cnt, ihead[N<<1], top, s[N<<1], n, m;
bool vis[N<<1];
void add(int u, int v) { e[++cnt]=(E){ihead[u], v}; ihead[u]=cnt; }
bool dfs(int x) {
if(vis[x^1]) return 0;
if(vis[x]) return 1;
vis[x]=1;
s[++top]=x;
for(int i=ihead[x]; i; i=e[i].next) if(!dfs(e[i].to)) return 0;
return 1;
}
bool work() {
int nn=n<<1;
for(int i=0; i<nn; i+=2) if(!vis[i] && !vis[i+1]) {
top=0;
if(!dfs(i)) {
while(top) vis[s[top--]]=0;
if(!dfs(i+1)) return 0;
}
}
for(int i=0; i<nn; ++i) if(vis[i]) printf("%d\n", i+1);
return 1;
}
int main() {
while(~scanf("%d%d", &n, &m)) {
for(int i=0; i<m; ++i) { int x, y; scanf("%d%d", &x, &y); --x; --y; add(x, y^1); add(y, x^1); }
if(!work()) puts("NIE");
cnt=top=0;
memset(vis, 0, sizeof(bool)*(n<<1));
memset(ihead, 0, sizeof(int)*(n<<1));
}
return 0;
}
本題很顯然的2-sat問題= =
對于關(guān)系（x,y）實際上就是滿足!(x & y)
即當(dāng)x=1時y必須為0，即連邊x->y'
當(dāng)y=1時x必須為1，即連邊y->x'
由于這個dfs的算法本身就是字典序最小了= =直接搞就行了= =
（媽呀難道這個算法是O(nm)的嘛QAQ看來得寫tarjan了以后= =（雖然字典序最小只能用這個O(nm)算法= =？）
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
