RT,Debug 调到自闭了……
思路就是一个人与其厌恶的人的同伴连边,跑强联通分量,如果在一个分量里就矛盾,否则输出方案。
代码里有适量注释,有人能帮帮忙么/kel
Code:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 40010;
struct edge{
int u, v, nxt;
}e[N << 1];
int head[N << 1], cnt, n, m, x, y, vis[N << 1], f[N << 1];
inline void add(int u, int v){
e[++cnt].u = u;
e[cnt].v = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
inline int anc(int x){
return x == f[x] ? x : f[x] = anc(f[x]);
}
inline void dfs(int u){
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(!vis[v]){
vis[v] = vis[u] + 1;
dfs(v);
}
int fu = anc(u), fv = anc(v);
if(vis[fv] > 0){
if(vis[fu] < vis[fv]) f[fv] = fu;
else f[fu] = fv;
}
}
vis[u] = -1;
}//跑强联通分量
int main(){
n = read(); m = read();
for(int i = 1; i <= m; ++i){
x = read(); y = read();
add(x, (y & 1) ? (y + 1) : (y - 1));
add(y, (x & 1) ? (x + 1) : (x - 1));
}//建图
for(int i = 1; i <= (n << 1); ++i) f[i] = i;//并查集初始化
for(int i = 1; i <= (n << 1); ++i){
if(!vis[i]){
vis[i] = 1;
dfs(i);
}
}
for(int i = 1; i <= n; ++i){
if(anc(2 * i - 1) == anc(2 * i)) return puts("NIE") & 0;
}//在一个强联通分量里,矛盾
for(int i = 1; i <= n; ++i){
if(anc(2 * i - 1) < anc(2 * i)) printf("%d\n", 2 * i - 1);
if(anc(2 * i - 1) > anc(2 * i)) printf("%d\n", 2 * i);
}//输出方案
return 0;
}