本文主要是介绍POJ 1703 简单的2SAT思想，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题没有用到2SAT的算法，不过用到了思想。挺好的，入门吧。
因为现在就是判断某两个人是不是在同一集合里，而2SAT正好就是解法这种问题的最好解法算法，其思想就是2个为布尔值的量一个真则另一个必假，一个假另一个必真。
所以设当前人为 i，则 i *2这个结点为真，那么根据2SAT，则 2*i+1为假。所以如果输入的a与b，如果!(a*2+1)&&b=true 或者 a&&!(b*2+1)=true则在不同的集合；如果a&&!(a*2+1)=true 或者 b&&!(b*2+1)=true，则为在同一集合里；否则为未确定。
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 1000005
#define MN 200010
#define INF 55566677
#define eps 1e-7
using namespace std;
typedef long long ll;
int f[MN];
int find(int x)
{return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{int t,n,m;sca(t);while(t--){sc(n,m);for(int i=1;i<=2*n+10;i++) f[i]=i;while(m--){char s[3];int x,y;scanf("%s%d%d",s,&x,&y);int x1=find(x*2);int y1=find(y*2);int x2=find(x*2+1);int y2=find(y*2+1);if(s[0]=='A'){if(x1==y2||x2==y1)puts("In different gangs.");else if(x1==y1||x2==y2)puts("In the same gang.");else puts("Not sure yet.");}else f[x1]=y2,f[x2]=y1;}}return 0;
}
这篇关于POJ 1703 简单的2SAT思想的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
