Codeforces Round #383 (Div. 2) E(貪心,二分圖染色,好題)

2019-11-08 02:01:26

字體：大中小

供稿：網(wǎng)友

題目鏈接E. Arpa’s overnight party and Mehrdad’s silent enteringtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

$\text{[math]}$

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.

Exampleinput

31 42 53 6output1 22 11 2
題意：
給出n，表示有2n個(gè)人圍成一圈坐在桌子邊上，對(duì)應(yīng)這2n個(gè)人是n對(duì)情侶，每個(gè)人占據(jù)一個(gè)位子，然后n行，每行兩個(gè)數(shù)，表示坐在這兩個(gè)位置的人是情侶，要求情侶不能吃同一種食物，并且桌子上相鄰的三個(gè)人的食物必須有兩個(gè)人是不同的，只有兩種食物（1或者是2），問一種可行分配方式。不能分配輸出-1.
題解：
一開始看別人的題解，都是說情侶之間連邊，2*i和2*i-1位置的人連邊，然后進(jìn)行二分染色，我照這個(gè)思路寫了代碼，然后A了，不過不知道為什么是2*i和2*i-1之間連邊。
其實(shí)，這樣的連邊一定能保證圖是個(gè)二分圖，即一定有可行分配方式，因?yàn)閳D中不存在長(zhǎng)度為奇數(shù)的環(huán)，所以是個(gè)二分圖，而且恰好這樣連邊也滿足了題意。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> 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<PII> 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;}