2-STA求解问题,2-SAT最重要的就是如果a与b矛盾,就加边a—>b',
因为新娘不能看到有不正当关系的两人,所以只需要在每对夫妇中选一个坐在新娘对面,
他们之间没有关系不正当的人。
#include<stdio.h>
#include<string.h>
#include<queue>
#include<stack>
#define N 500
using namespace std;
int n,m,low[N],dfs[N],ins[N],belong[N],link[N];
int ans,idx,first[N],first1[N],num,num1,cf[N],color[N],indeg[N];
struct eage
{
int ed,next;
}E[N*N],E1[N*N];
void addeage(int x,int y)
{
E......
阅读全文