2-SAT

2-SAT其實是2-satisfaction，不是2-setㄛ~

先輩知識 : SCC演算法

題目 : 有N個人，每個人都有兩個要求(要或不要)，只要達到一個以上的要求就算滿足，請問有沒有辦法滿足所有人，並輸出一種可能的方法。

建邊

假設每個人的狀態為:

+ A - B

代表 要A不要B

那麼要滿足這個人就要達成他其中一個條件 :

如果條件A沒有達到那條件B一定要符合 : -A -> +B
如果條件B沒有達到那條件A一定要符合 : -B -> +A

這樣就能保證滿足這個人，且建邊的條件一定是只有一條路，如果是建+A，B就可有可無，會有兩條路。我們建邊的用意是當滿足這個條件時可以推倒到另一個保證滿足的條件。

判斷條件是否成立

假設建完邊的圖是:

如果+A成立會導致-A成立，且-A成立會導致+A成立，不管從哪個出發都會產生矛盾，像這樣的情況我們就找不到一組合理的解，且其性質就剛好符合SCC:如果任兩點都有路徑可互相抵達就表示為一個SCC。

因此我們得出了一個結論:如果一個條件的+-都在同一個SCC中，則該條件不成立!

那我們就可以先利用SCC演算法來判定是否能成立，之後再把所有不互相矛盾的SCC更新到答案就好了。

構造答案

如果+-不在同一個SCC，那要用哪個SCC來更新答案呢?

如果是以Tarjan演算法來時做，做完的SCC編號會是反向的拓譜排序，因為要遞迴完所有子樹才會判斷能不能繞上去，所以在越靠近葉節點的地方會越快被生成SCC，SCC的編號也就越小，所以1號會在最下面，那我們就是要利用拓譜序值來決定用哪個SCC，假設Tarjan完的SCC走向是SCC(a)->SCC(b)，a是比較上面(靠近root)的節點，拓譜排序值較大，b是比較下面(靠近葉節點)的節點，拓譜排序值較小，因為只能從a->b，所以為了不要矛盾，我們應該取b，才不會因為a成立導致b也可能成立。

像這樣連成一條線的，分別為3個不同的SCC(雖然+A可以走到-A，但-A不能走到+A所以不是一個SCC)，那我們為了保證答案一定成立，會選擇比較下游的，雖然"+A可以導致-A"，但只要我們選"-A不能導致+A"，這樣就不會產生矛盾了。

如果是利用Kosaraju演算法就只要再判斷的時候用拓譜排序值較大的就好了。


































































#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define MAXN 200005
 
vector<int> Graph[MAXN];
int scc[MAXN],dfn[MAXN],up[MAXN],id,sccid;
bool instk[MAXN];
stack<int> stk;
 
void tarjan(int now){  //Tarjan's Algorithm
	stk.push(now);
	instk[now]=true;
	dfn[now]=up[now]=++id;
	
	for(auto i:Graph[now]){
		if(!instk[i] && dfn[i]) continue;
		if(!dfn[i]) tarjan(i);
		up[now]=min(up[now],up[i]);
	}
	
	if(up[now]==dfn[now]){
		int x;
		sccid++;
		do{
			x=stk.top();stk.pop();
			instk[x]=false;
			scc[x]=sccid;
		}while(x!=now);
	}
}
 
int main(){
	int n,m;
	cin >> m >> n;
	for(int i=0;i<m;i++){
		char c1,c2;
		int x,y;
		cin >> c1 >> x >> c2 >> y;
        
               //-3 -> 3
               //+3 -> n+3
               //mask:決定要不要加n
		int maskx=(c1=='+');
		int masky=(c2=='+');
		
		Graph[x+n*(maskx^1)].pb(y+n*masky);  //X不成立，Y一定要成立
		Graph[y+n*(masky^1)].pb(x+n*maskx);  //Y不成立，X一定要成立
	}
	
	for(int i=1;i<=n*2;i++){  //有n個條件，每個條件都有+-
		if(!dfn[i]) tarjan(i);
	}
	
	for(int i=1;i<=n;i++){
		if(scc[i]==scc[i+n]){ //判斷同一個條件的+-有沒有在同一個SCC
			cout << "IMPOSSIBLE\n";
			return 0;
		}
	}
	
	for(int i=1;i<=n;i++){
		cout << (scc[i]<scc[i+n]?'-':'+') << ' ';  //如果-拓譜排序值較小(較下游)就用-，否則用+。
    }
}
Select a repo