首页 > 代码库 > Codeforces Round #383 (Div. 1) C(二分图)
Codeforces Round #383 (Div. 1) C(二分图)
一道很巧妙的二分图的题目
简单分析性质可知,一个合法序列一定是由12,21这样的子串构成的,所以相邻的每隔2个两两配对
然后BF和GF互相配对,思考一下,如果存在奇环,那么必定有一个BG有两个GF,或者一个GF有两个BF,所以不存在这种情况,一定有解
直接二分图判断即可
#include <iostream> #include <cstdio> #include <vector> #define mp make_pair #define fi first #define se second using namespace std; const int maxn = 200050; vector<int> G[maxn]; int color[maxn]; vector <pair <int, int>> Q; void dfs(int x) { for(auto to : G[x]) { if(!color[to]) { color[to] = color[x] == 1 ? 2 : 1; dfs(to); } } } int n, x, y; int main() { scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d %d", &x, &y); x--; y--; G[x].push_back(y); G[y].push_back(x); Q.push_back(mp(x, y)); } for(int i = 0; i < n; i ++) G[2*i].push_back(2*i+1), G[2*i+1].push_back(2*i); for(int i = 0; i < 2*n; i++) if(!color[i]) { color[i] = 1; dfs(i); } for(auto x : Q) printf("%d %d\n", color[x.fi], color[x.se]); }
Codeforces Round #383 (Div. 1) C(二分图)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。