Codeforces Round #383 (Div. 2) E(贪心,二分图染色,好题)
发布日期:2021-11-12 00:25:50 浏览次数:2 分类:技术文章

本文共 3276 字,大约阅读时间需要 10 分钟。


E. Arpa’s overnight party and Mehrdad’s silent entering
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Note that girls in Arpa’s land are really attractive.

Arpa loves overnight parties. In the middle of one of these parties Mehrdad suddenly appeared. He saw n pairs of friends sitting around a table. i-th pair consisted of a boy, sitting on the ai-th chair, and his girlfriend, sitting on the bi-th chair. The chairs were numbered 1through 2n in clockwise direction. There was exactly one person sitting on each chair.

There were two types of food: Kooft and Zahre-mar. Now Mehrdad wonders, was there any way to serve food for the guests such that: 

  • Each person had exactly one type of food, 
  • No boy had the same type of food as his girlfriend, 
  • Among any three guests sitting on consecutive chairs, there was two of them who had different type of food. Note that chairs 2n and 1 are considered consecutive. 

Find the answer for the Mehrdad question. If it was possible, find some arrangement of food types that satisfies the conditions.

Input

The first line contains an integer n (1  ≤  n  ≤  105) — the number of pairs of guests.

The i-th of the next n lines contains a pair of integers ai and bi (1  ≤ ai, bi ≤  2n) — the number of chair on which the boy in the i-th pair was sitting and the number of chair on which his girlfriend was sitting. It's guaranteed that there was exactly one person sitting on each chair. 

Output

If there is no solution, print -1.

Otherwise print n lines, the i-th of them should contain two integers which represent the type of food for the i-th pair. The first integer in the line is the type of food the boy had, and the second integer is the type of food the girl had. If someone had Kooft, print 1, otherwise print 2.

If there are multiple solutions, print any of them.

Example
input
31 42 53 6
output
1 22 11 2


题意

给出n,表示有2n个人围成一圈坐在桌子边上,对应这2n个人是n对情侣,每个人占据一个位子,然后n行,每行两个数,表示坐在这两个位置的人是情侣,要求情侣不能吃同一种食物,并且桌子上相邻的三个人的食物必须有两个人是不同的,只有两种食物(1或者是2),问一种可行分配方式。不能分配输出-1.


题解:

一开始看别人的题解,都是说情侣之间连边,2*i和2*i-1位置的人连边,然后进行二分染色,我照这个思路写了代码,然后A了,不过不知道为什么是2*i和2*i-1之间连边。

其实,这样的连边一定能保证图是个二分图,即一定有可行分配方式,因为图中不存在长度为奇数的环,所以是个二分图,而且恰好这样连边也满足了题意。


#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define rep(i,a,n) for (int i=a;i
          
           =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
           
             VI;typedef long long ll;typedef pair
            
              PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=2e5+100;int head[maxn];struct edge{
             
int to,next;}e[maxn*10];   //int tol=0;void add(int u,int v){
e[++tol].to=v,e[tol].next=head[u],head[u]=tol;}int c[maxn];bool dfs(int u,int v){
c[u]=v;
for(int i=head[u];i;i=e[i].next)
{
int vv=e[i].to;
if(c[vv]&&c[vv]==v) return false;
else if(!c[vv]&&!dfs(vv,3-v))
return false;
}
return true;}vector  V;int main(){
int n;
scanf("%d",&n);
rep(i,1,n+1)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
V.pb(make_pair(u,v));
}
for(int i=2;i<=2*n;i+=2)
{
add(i,i-1),add(i-1,i);
}
memset(c,0,sizeof(c));
rep(i,1,2*n+1)
{
if(!c[i])
{
if(!dfs(i,1))
{
puts("-1");
return 0;
}
}
}
rep(i,0,n)
{
int u=V[i].first,v=V[i].second;
printf("%d %d\n",c[u],c[v]);
}
return 0;}


转载地址:https://blog.csdn.net/fouzhe/article/details/56011264 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Codeforces Beta Round #3 D. Least Cost Bracket Sequence(贪心,想法,好题)
下一篇:Codeforces Beta Round #50 C. First Digit Law(概率dp,好题)

发表评论

最新留言

关注你微信了!
[***.119.140.103]2022年05月31日 01时53分30秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章