这道题题意就是给你n对人，一对中编号为x，x+1，给你m对矛盾，表示这两个人不能同时选。
然后就是Two-Sat的模板题了，就是根据对称性，连边，加缩点，最后拓扑排序，求出一组可行解就可以了。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<queue> 6 #include<cstring> 7 8 using namespace std; 9 10 typedef pair<int,int>pai; 11 const int NN=8007,MM=20007,INF=1e9+7; 12 13 bool flag=0; 14 int n,m; 15 int cnt=0,head[NN*2],next[MM*2],rea[MM*2],cntr=0,headr[NN*2],nextr[MM*2],rear[MM*2]; 16 int Time,top,low[NN*2],dfn[NN*2],minnum[NN*2],stack[NN*2],instack[NN*2]; 17 int sz,belong[NN*2]; 18 int fan[NN*2],ru[NN*2]; 19 queue<int>ve[NN*2]; 20 21 struct Node 22 { 23 int x,y; 24 }a[MM]; 25 26 void add(int u,int v) 27 { 28 cnt++; 29 next[cnt]=head[u]; 30 head[u]=cnt; 31 rea[cnt]=v; 32 } 33 void add2(int u,int v) 34 { 35 cntr++; 36 nextr[cntr]=headr[u]; 37 headr[u]=cntr; 38 rear[cntr]=v; 39 } 40 void Tarjan(int u) 41 { 42 dfn[u]=low[u]=++Time; 43 stack[++top]=u,instack[u]=true; 44 for (int i=head[u];i!=-1;i=next[i]) 45 { 46 int v=rea[i]; 47 if (dfn[v]==0) 48 { 49 Tarjan(v); 50 low[u]=min(low[v],low[u]); 51 } 52 else if (instack[v]) low[u]=min(low[u],dfn[v]); 53 } 54 if (low[u]==dfn[u]) 55 { 56 int x=-1; 57 minnum[++sz]=INF;; 58 while (!ve[sz].empty()) ve[sz].pop(); 59 while (x!=u) 60 { 61 x=stack[top--]; 62 belong[x]=sz; 63 minnum[sz]=min(minnum[sz],x);//记录最小编号，发现对称的那个环的最小编号应该是该环最小编号的fan 64 ve[sz].push(x); 65 instack[x]=false; 66 } 67 } 68 } 69 void rebuild() 70 { 71 for (int i=1;i<=2*n;i++) 72 for (int j=head[i];j!=-1;j=next[j]) 73 { 74 int v=rea[j]; 75 if (belong[i]!=belong[v]) 76 { 77 ru[belong[v]]++; 78 add2(belong[i],belong[v]); 79 } 80 }//重构 81 } 82 bool cmp(int x,int y) 83 { 84 return x<y; 85 } 86 void solve() 87 { 88 int ans[NN*2]; 89 queue<int>q; 90 while (!q.empty()) q.pop(); 91 for (int i=1;i<=sz;i++) 92 if (!ru[i]) q.push(i); 93 bool biao[NN*2]={0}; 94 top=0; 95 while(!q.empty()) 96 { 97 int u=q.front(); 98 if (!biao[fan[minnum[u]]]) ans[++top]=u,biao[minnum[u]]=1; 99 q.pop(); 100 for (int i=headr[u];i!=-1;i=nextr[i]) 101 { 102 int v=rear[i]; 103 ru[v]--; 104 if (!ru[v]) q.push(v); 105 } 106 }//拓扑的一个过程 107 bool booo=0; 108 int res[NN],ll=0; 109 for (int i=1;i<=top;i++) 110 { 111 int x=ans[i]; 112 while(!ve[x].empty()) 113 { 114 res[++ll]=ve[x].front(); 115 ve[x].pop(); 116 } 117 }//ll最终等于n 118 sort(res+1,res+ll+1,cmp); 119 for (int i=1;i<=ll;i++) 120 printf("%d ",res[i]); 121 } 122 void init() 123 { 124 cntr=cnt=top=Time=sz=flag=0; 125 memset(dfn,0,sizeof(dfn)); 126 memset(head,-1,sizeof(head)); 127 memset(headr,-1,sizeof(headr)); 128 memset(ru,0,sizeof(ru)); 129 for (int i=1;i<=2*n;i++) 130 if (i%2==1) fan[i]=i+1; 131 else fan[i]=i-1; 132 for (int i=1;i<=m;i++) 133 { 134 scanf("%d%d",&a[i].x,&a[i].y); 135 add(fan[a[i].y],a[i].x); 136 add(fan[a[i].x],a[i].y);//刚开始连反向边并不影响正确率，而且在拓扑的时候不需要反向标记，方便许多。 137 } 138 } 139 void pan() 140 { 141 for (int i=1;i<=2*n;i+=2) 142 if (belong[i]==belong[fan[i]])//如果一个块中，有编号一组的点，绝对不可以满足。 143 { 144 flag=1; 145 return; 146 } 147 } 148 int main() 149 { 150 while (~scanf("%d%d",&n,&m)) 151 { 152 init();//初始化非常重要。 153 for (int i=1;i<=n*2;i++) 154 if (dfn[i]==0) Tarjan(i);//tarjan一次 155 pan(); 156 if (flag) 157 { 158 printf("NIE "); 159 continue; 160 } 161 rebuild(); 162 solve(); 163 } 164 }