http://cogs.pro:8080/cogs/problem/problem.php?pid=pyzQimjkj
题意：有n个集合，每个集合有俩元素，要从n个中各选一个放一堆，但是有的俩不能同时取，让你找出一种选取方案。
思路：2-SAT板子，主要学一下这个算法。算法流程：
构图：若a,b不能同时选，连a->b'和b->a'
求图的极大强连通子图：直接tarjan。
缩点然后变成个新的DAG：因为一个强连通分量里选一个其他都要选，一个不选其他都不能选，所以直接缩成一个点。
对新图拓排：要存反边，这个一开始不造为啥，后来看解释是因为传递的是不选择标记，这边往前代走，对面那边往后代走（对这个起作用）。。选一个他后代都得选，不选谁谁的前代都不能选，so...
自底向上进行选择，删除。
输出。
#include<bits/stdc++.h>
#define oth(x) x&1?x+1:x-1
using namespace std;
const int N = 20010; struct Edge{
int to,nxt;
}e[50010];
int head[N],dfn[N],low[N],st[N],bel[N];
bool vis[N];
int ru[N],q[N],opp[N],pr[N];
int tot_edge,n,nn,m,tot_node,top,cnt_block,L,R;
vector<int>mp[N]; inline int read() {
int x = 0,f = 1;char ch = getchar();
for (; ch<'0'||ch>'9'; ch=getchar()) if(ch=='-') f=-1;
for (; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
return x * f;
}
void add_edge(int u,int v){
e[++tot_edge].to = v;
e[tot_edge].nxt = head[u];
head[u] = tot_edge;
}
void tarjan(int u){
dfn[u] = low[u] = ++tot_node;
st[++top] = u;
vis[u] = true;
for(int i=head[u];i;i=e[i].nxt){
int v = e[i].to;
if(!dfn[v]){
tarjan(v);
low[u] = min(low[v],low[u]);
}
else if(vis[v])
low[u] = min(dfn[v],low[u]);
}
if(low[u]==dfn[u]){
++cnt_block;
do{
vis[st[top]] = false;
bel[st[top]] = cnt_block;
top--;
}while(st[top+1]!=u);
}
}
void topsort(){
L=1;R=0;
for(int i=1;i<=cnt_block;i++){
if(ru[i]==0) q[++R] = i;
}
while(L<=R){
int u = q[L++];
if(pr[u]) continue;
pr[u] = 1;pr[opp[u]] = 2;
int sz = mp[u].size();
for(int i=0;i<sz;i++){
int v = mp[u][i];
ru[v]--;
if(ru[v]==0) q[++R] = v;
}
}
}
bool work(){
for(int i=1;i<=nn;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=nn;i++){
if(bel[i]==bel[oth(i)]) return false;
opp[bel[i]] = bel[oth(i)];
opp[bel[oth(i)]] = bel[i];
}
for(int u=1;u<=nn;u++){
for(int i=head[u];i;i=e[i].nxt){
int v = e[i].to;
if(bel[u]!=bel[v]){
ru[bel[u]]++;
mp[bel[v]].push_back(bel[u]);
}
}
}
topsort();
return true;
}
int main(){
freopen("spo.in","r",stdin);
freopen("spo.out","w",stdout);
n = read(),m = read(),nn = n<<1;
for(int i=1;i<=m;i++){
int a = read(),b = read();
add_edge(a,oth(b));
add_edge(b,oth(a));
}
if(work()){
for(int i=1;i<=nn;i++){
if(pr[bel[i]]==1) cout<<i<<endl;
}
}
else puts("NIE");
return 0;
}