
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAABcAAAAXCAYAAADgKtSgAAAFCUlEQVR42n2VeVCUdRzGf3n0T/80ldqITqk0gGhrXqSjTjbTaDWalVhOajp5pOMR3gjqeuExaDKYCKmJqSCGgQZIyaFQKseC67ELHhwSrC7HGpTG7r6f3u86iISyM8+8z3y/z/N5d993dn4KaKcso+rS4pXiOdtMNbBhqZpxf5UKFYmXmezad1rVHi4hCausLvdD1OKmncr8MNZP47cv4cJyROJlJjvJSLal+2x4guos19pl/sOawpWZ9Alw4wDYMsBR4KLR3CwSLzPZSUay0nmSIWr3jRtCvSc+iFZQtBrsZ3XQRRf1uRp156AuG5F4mclOMpKVjnSfZLV5XjVB/sMfxCgoXgH2lGZsyVD9E9Qkgu1kG8lMdpKRrHSkK4wWpgLleSlGFfh8U4S6wh8ToHJ/s1axH60iBu7s71CSkax0pNuoM4QlzMc/oW7ja0tJ7QFXv2nm9g69uBUqt8GtsI4lGclKR7opPajb9HrQ48eifzo3RvW8Ru5wsC5ycXMZltPTufrLLChdhmYJAuvSNpKZ7CQjWelIVxjCEqYHXv71i289PNIHLo2Gq9O0uA0B7Fk7Ftul2WDVi+apaMWfweUpiMTLTHaSkax0pCsMYQnTA682vjSbM/5gGu06tXUAyVEjwPo+jvOjsP06HGfeSCgehZY3ApF4mclOMljHIx3pCkNYNp3pgdu3vLKRnEE0ZLzjzIz1pexML5YEzmPxe0MxTlJs/rwHJScGg2mMSLzMZKdnhrA4cAG30/qQFfuGzhjrFJYwPfDasG6byBwGhV2d97ICCN6dzrvhVm6cncpfpgDMqWMwJQ0F00hERbo3p47WdyO4nTGZ8TstBEdmUJMxBgqUk8yh1Ib12OSBV67znk+64vKJJa71x69RWA+Hs8uwxivcBQqu94JSb7jaB0Ql/fRrT1z5Ckuc4lDmTYocsP6ElcLjy12kKSo39J3vgTtWqyFxO3Zrn6TWc+4emgTXJljYunK1/rJmExU6iR/Wv82xLQaObTZwcN1IotZ8TOTaeWxbFUxI/DVMDZBjR5uS7iB22x7sK9VQD1wNi/H3i690nrgDF+65tfQqjRXHLRSaiqmsqqbGVou9tgGHo4mGhkbs9nqqa+yUV1aRX1DI8rhrpOkd6SZWwcCEKrca96PhEXxO2rjgi3+TUkNzjs2tRVg0fFemsGvuKA5FR3AmJZkiUwGlJRZKdBUW5JF66iQHvgsnfNYgvJcmsfO6Rs5dt5Zazb+heQ9QC9InPIKrFa9OjrM6Dv8JkTdwGZLuug9EBpE0U5E4Q3FkumLfp4rIibo+UkRPVhzV54lfKJLmKI7FLGRgYo07ohSXMALjrI1KhXgpZaQToNS8ox8E7CvMD4rOJjt+DZR1dZVkDyYt1Jfc0P4UhPlh2u6LKH+LHzkh/Ukz+nDr9yFQ3tWZG7+CZVEZDN+bn6fmxn3Y+ven9UTJnqoWaT8rMBugwuCstQxwm073085F9yZzlxeZ33px/vveXE7tpzVYB7i5/aaTYgOcVOROUwuBx8zWUyMhoXOLz/pq0KS6mF4V5PpAyUC5Ca47g1z/lBucIvGUG8AyAHJ8qIvxqjird/7PanvmKWMnEKF8lOpZurH79rqDvSqaT/WFi75g7o9IfHNyX2Rn3dB9R289Kx3pyrn6zDO03VGlVLez014Yf2XNy8FlW7rvFYmXmeye1ukQLjIaVScQoTqSZCT7tN1/5TypNXepA58AAAAASUVORK5CYII=" alt="" />
按字典序输出 直接dfs就好了(hdu1814(抄自 http://www.cnblogs.com/kuangbin/archive/2012/10/05/2712429.html)
#include <bits/stdc++.h>
using namespace std; const int MAXN = ;
const int MAXM = ; struct Edge {
int to, next;
} edge[MAXM];
int head[MAXN], cntE; void init() {
cntE = ;
memset(head, -, sizeof head);
} void addedge(int u, int v) {
edge[cntE].to = v;
edge[cntE].next = head[u];
head[u] =cntE++;
} bool vis[MAXN];
int stk[MAXN], top;
bool dfs(int u) {
if (vis[u^]) return false;
if (vis[u]) return true;
vis[u] = true; stk[top++] = u;
for (int i = head[u]; ~i; i = edge[i].next) {
if (!dfs(edge[i].to)) return false;
}
return true;
} bool sat(int n) {
memset(vis, false, sizeof vis);
for (int i = ; i < n; ++i) {
if (vis[i] || vis[i ^ ]) continue;
top = ;
if (!dfs(i)) {
while (top) vis[stk[--top]] = false;
if (!dfs(i^)) return false;
}
}
return true;
} int main() {
int n, m;
int u, v;
while (~scanf("%d%d", &n, &m)) {
init();
while (m--) {
scanf("%d%d", &u, &v);
u--, v--;
addedge(u, v^); //选u就必须选择v^1
addedge(v, u^);
}
n *= ;
if (sat(n)) {
for (int i = ; i < n; ++i) {
if (vis[i]) printf("%d\n", i+);
}
} else {
printf("NIE\n");
}
}
return ;
}
输出任意一组解
const int N = ;
const int M = ; struct Edge {
int from, to, next;
} edge[M], edge2[M];
int head[N];
int cntE, cntE2;
void addedge(int u, int v) {
edge[cntE].from = u; edge[cntE].to = v; edge[cntE].next = head[u]; head[u] = cntE++;
}
void addedge2(int u, int v) {
edge2[cntE2].from = u; edge2[cntE2].to = v; edge2[cntE2].next = head[u]; head[u] = cntE2++;
} int dfn[N], low[N], idx;
int stk[N], top;
int in[N];
int kind[N], cnt; void tarjan(int u)
{
dfn[u] = low[u] = ++idx;
in[u] = true;
stk[++top] = u;
for (int i = head[u]; i != -; i = edge[i].next) {
int v = edge[i].to;
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (in[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++cnt;
while () {
int v = stk[top--]; kind[v] = cnt; in[v] = false;
if (v == u) break;
}
}
} int opp[N], ind[N], col[N]; // 相对的点 入度 染色 col[]=1选择 bool topsort(int n) // 序号从0开始
{
for (int i = ; i < *n; i += ) {
int k1 = kind[i]; int k2 = kind[i^]; // 相对的两个点
if (k1 == k2) return false;
opp[k1] = k2; opp[k2] = k1;
}
memset(head, -, sizeof head);
int u, v;
for (int i = ; i < cntE; ++i) {
u = edge[i].from, v = edge[i].to;
if (kind[u] != kind[v]) { // 反向建图
addedge2(kind[v], kind[u]);
ind[kind[u]]++;
}
}
queue<int> q;
for (int i = ; i <= cnt; ++i) if (!ind[i]) q.push(i);
while (q.size()) {
u = q.front(); q.pop();
if (!col[u]) col[u] = , col[ opp[u] ] = -;
for (int i = head[u]; i != -; i = edge2[i].next)
if (--ind[edge2[i].to] == ) q.push(edge2[i].to);
}
return true;
} void init() {
cntE = cntE2 = ;
memset(head, -, sizeof head);
memset(dfn, , sizeof dfn);
memset(in, false, sizeof in);
idx = top = cnt = ;
memset(ind, , sizeof ind);
memset(col, , sizeof col);
}