//暴力DFS，求字典序最小的解，也是求字典序唯一的方法 #include<cstdio> #include<cstring> #include<vector> using namespace std; const int maxn=10000+10; struct TwoSAT {int n;//原始圖的節(jié)點數(shù)(未翻倍)vector<int> G[maxn*2];//G[i]==j表示如果mark[i]=true,那么mark[j]也要=truebool mark[maxn*2];//標(biāo)記int S[maxn*2],c;//S和c用來記錄一次dfs遍歷的所有節(jié)點編號void init(int n){this->n=n;for(int i=0;i<2*n;i++) G[i].clear();memset(mark,0,sizeof(mark));}//加入(x,xval)或(y,yval)條件//xval=0表示假，yval=1表示真void add_clause(int x,int xval,int y,int yval){x=x*2+xval;y=y*2+yval;G[x^1].push_back(y);G[y^1].push_back(x);}//從x執(zhí)行dfs遍歷,途徑的所有點都標(biāo)記//如果不能標(biāo)記,那么返回falsebool dfs(int x){if(mark[x^1]) return false;//這兩句的位置不能調(diào)換if(mark[x]) return true;mark[x]=true;S[c++]=x;for(int i=0;i<G[x].size();i++)if(!dfs(G[x][i])) return false;return true;}//判斷當(dāng)前2-SAT問題是否有解bool solve(){for(int i=0;i<2*n;i+=2)if(!mark[i] && !mark[i+1]){c=0;if(!dfs(i)){while(c>0) mark[S[--c]]=false;if(!dfs(i+1)) return false;}}return true;} };

?

總結(jié)

以上是生活随笔為你收集整理的图论--2-SAT--暴力染色法模板（字典序最小解) RQ的板子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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