[ural 1129] 欧拉回路

题意：

幼儿园里有许多房间，之间是走廊和门。一个装修计划即将执行。 这些门允许涂上明快的颜色：绿色和黄色。园长希望满足以下条件：任意一扇门的各个面必须不同颜色。每一个房间绿色门的数量，与黄色门的数量之差最多为1。给定园长的计划，请提出你的安排。

分析：

首先，对于无向图，度为奇数的点必然有偶数个。

下面证明一下：

如果加入边(i,j)，有下面几种情况：

1、两个点原来的度一奇一偶，那么加入边以后，度为奇数的点的数量没变

2、两个点原来的度都是奇数，加入边后，度为奇数的点的数量-2

3、两个点原来的度都为偶数，加入边后，度为奇数的点的数量+2

由于只有3个种情况-2,+0,+2，所以，度为奇数的点的数量必为偶数个。

于是命题得证。

然后我们对度为奇数的同一连通分量的点连边，这样就使图不存在度为奇数的点了。

于是我们利用欧拉回路可以使颜色数量相等。

最后我们把加的边删掉。

由于每个点都只会加一条边，所以G和Y的差距不会超过1。

code：

#include #include struct gtp{int color,next;}c[100000];
int g[101][101],n,ls[101][101],ct,du[101],L[100000],Lt,a[101][101],e=0,v[101];
bool flag[101];

void init(){
    memset(g,0,sizeof(g));
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        int num,tmp;
        scanf("%d",&num);
        for (int j=1;j<=num;j++){
            scanf("%d",&tmp);
            g[i][tmp]++;
        }   
    }   
}   

void dfs(int k){
    for (int i=1;i<=n;i++)
      if (a[i][k]>0){
          a[i][k]–;
          a[k][i]–;
          dfs(i);
      }   
    L[++Lt]=k;
}   

void filldfs(int k){
    for (int i=1;i<=n;i++)
      if (g[k][i]>0 && v[i]==0){
          v[i]=v[k];
          filldfs(i);
      }           
}   

void fill_color(){
    memset(v,0,sizeof(v));
    for (int i=1;i<=n;i++)
      if (v[i]==0) {
          v[i]=++ct;
          filldfs(i);
      }   
}   

void addcolor(int x,int y){
    e++;
    c[e].color=0;
    c[e].next=ls[x][y];
    ls[x][y]=e;
    e++;
    c[e].color=1;
    c[e].next=ls[y][x];
    ls[y][x]=e;
}   

void eur(){
    memset(du,0,sizeof(du));
    memcpy(a,g,sizeof(g));
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        if (g[i][j]>0) du[j]+=g[i][j];
    for (int i=1;i<=n;i++)
      if (du[i]%2==1)
        for (int j=i+1;j<=n;j++)
          if (du[j]%2==1 && v[i]==v[j]){
              du[i]++;
              du[j]++;
              a[i][j]++;
              a[j][i]++;
              break;
          }
    memset(flag,false,sizeof(flag));
    for (int i=1;i<=n;i++)
      if (!flag[v[i]]){
        flag[v[i]]=true;
        Lt=0;
        dfs(i);
        for (int j=1;j          addcolor(L[j],L[j+1]);
    }   
}   

void print(){
    for (int i=1;i<=n;i++){
      for (int j=1;j<=n;j++){
          int t=ls[i][j];
          for (int num=g[i][j];num>=1;num–){
              if (c[t].color==0) printf("G ");
                            else printf("Y ");
              t=c[t].next;
          }   
      }       
      printf("n");
}   
}   

int main(){
    init();
    fill_color();
    eur();
    print();
}