社交网站开发背景,福州网站设计企业建站,网站二次开发公司,系统小说正题
题目链接:https://www.luogu.com.cn/problem/P5782 题目大意 nnn对人#xff0c;每对之间恰好有一个人出席。mmm对仇恨关系表示两个人不能同时出席。
求是否有解并输出。 1≤n≤8000,1≤m≤200001\leq n\leq 8000,1\leq m\leq 200001≤n≤8000,1≤m≤20000 解题思路
裸…正题
题目链接:https://www.luogu.com.cn/problem/P5782 题目大意
nnn对人每对之间恰好有一个人出席。mmm对仇恨关系表示两个人不能同时出席。
求是否有解并输出。
1≤n≤8000,1≤m≤200001\leq n\leq 8000,1\leq m\leq 200001≤n≤8000,1≤m≤20000 解题思路
裸的2-SAT\text{2-SAT}2-SAT。AJ的任务罢了。
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N3e510;
struct node{int to,next;
}a[N2];
int n,m,tot,cnt,num,ls[N],dfn[N],low[N],col[N];
bool ins[N];stackint s;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void tarjan(int x){dfn[x]low[x]cnt;s.push(x);ins[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(!dfn[y]){tarjan(y);low[x]min(low[x],low[y]);}else if(ins[y])low[x]min(low[x],dfn[y]);}if(dfn[x]low[x]){num;while(s.top()!x){ins[s.top()]0;col[s.top()]num;s.pop();}col[x]num;ins[x]0;s.pop();}return;
}
int main()
{scanf(%d%d,n,m);n*2;for(int i1;in;i2)addl(in,i1),addl(i1n,i),addl(i1,in),addl(i,i1n);for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(x,yn);addl(y,xn);}for(int i1;i2*n;i)if(!dfn[i])tarjan(i);for(int i1;in;i)if(col[i]col[in])return puts(NIE)0;for(int i1;in;i)if(col[i]col[in])printf(%d\n,i);return 0;
}
