UVA - 1627

明らかに本題はまず認識しないでエッジを再構築しなければならない(両者uはvを認識しているがvはuを認識していないのも認識していない)それから2点マッチングして、マッチングに成功して、2つのグループに分けることができる.
次の問題はリュックサックの問題で、連通成分ごとに1色に着色された部分を選択すると、その連通成分が残っている人は別のグループにしかいないので、第1グループが第2グループより多く(num(1)-num(2))個人が増加していると見なすことができる.このように
問題はすべての連通成分のリュックサックの選択です.
境界の注意

    #include <map>  
    #include <cstdio>  
    #include <vector>  
    #include <cstdlib>  
    #include <cstring>  
    #include <iostream>  
    #include <algorithm>  
    using namespace std;  
    const int maxn = 105;  
    vector<int> son[maxn],bag,st[maxn][2];  
    bool vis[maxn],G[maxn][maxn];  
    int color[maxn],n;  
    bool bipartite(int u,int cnt){  
    for(int i=1;i<=n;i++)if(G[u][i]){  
          int v = i;  
          if(color[v]){  
             if(color[v] == color[u]) return false;  
             continue;  
          }  
          color[v] = 3 - color[u];  
          st[cnt][color[v]-1].push_back(v);  
          if(!bipartite(v,cnt)) return false;  
    }  
    return true;  
    }  
    const int ADD = 101;  
    int d[maxn][maxn*2+4][2];  
    bool VIS[maxn][maxn*2+4][2];  
    int dp(int i,int j,int k){  
    if(VIS[i][j][k]) return d[i][j][k];  
    VIS[i][j][k] = true;  
      
    int& ans = d[i][j][k];  
    if(i==bag.size() - 1) {return d[i][j][k] =0;}  
    int now = j - ADD;  
    int ans1 = dp(i+1,ADD+(now-bag[i+1]),0) + bag[i+1];  
    int ans2 = dp(i+1,ADD+(now+bag[i+1]),1) - bag[i+1];  
    ans = abs(now - ans1) < abs(now - ans2) ? ans1 : ans2;  
    return ans;  
    }  
    vector<int> ans;  
    void print_ans(int i,int j,int k){  
    if(i == bag.size() - 1)  return ;  
    if(d[i][j][k] == dp(i+1,ADD+(j-ADD-bag[i+1]),0) + bag[i+1]){  
           for(int g=0;g<st[i+1][0].size();g++)  
               ans.push_back(st[i+1][0][g]);  
               print_ans(i+1,ADD+(j-ADD-bag[i+1]),0);  
    }  
    else {  
        for(int g=0;g<st[i+1][1].size();g++)  
               ans.push_back(st[i+1][1][g]);  
               print_ans(i+1,ADD+(j-ADD+bag[i+1]),1);  
    }  
    }  
    int main(){  
        //freopen("input.txt","r",stdin);  
        int T,kase=0;  
        scanf("%d",&T);  
        while(T--){  
            if(kase++) printf("
");  
            scanf("%d",&n);  
            for(int i=1;i<=n;i++) son[i].clear();  
            for(int i=1;i<=n;i++){  
                 int x;  
                 while(scanf("%d",&x)&&x){  
                      son[i].push_back(x);  
                 }  
            }  
            memset(G,false,sizeof(G));  
            for(int i=1;i<=n;i++){  
                  memset(vis,false,sizeof(vis));  
                  for(int j=0;j<son[i].size();j++) vis[son[i][j]] = true;  
                  for(int j=1;j<=n;j++)if(j!=i){  
                       if(!vis[j]){  
                          G[i][j] = G[j][i] = true;  
                       }  
                  }  
            }  
            memset(color,0,sizeof(color));  
            bool flag=true;  
            bag.clear(); bag.push_back(0);  
            for(int i=1;i<=n;i++){  
                 if(!color[i]){  
                      int cnt = bag.size();  
                      st[cnt][0].clear();  
                      st[cnt][1].clear();  
                      color[i] = 1; st[cnt][0].push_back(i);  
                        if(!bipartite(i,cnt)){  
                             flag=false; break;  
                        }  
                        int c1=st[cnt][0].size();  
                        int c2=st[cnt][1].size();  
                        bag.push_back(c1 - c2);  
                    }  
                 }  
            if(!flag){  
                  printf("No solution
");  continue;  
            }  
            memset(VIS,false,sizeof(VIS));  
            dp(0,ADD,0);  
            ans.clear(); print_ans(0,ADD,0);  
            memset(vis,false,sizeof(vis));  
            printf("%d",ans.size());  
            for(int i=0;i<ans.size();i++) {printf(" %d",ans[i]);  vis[ans[i]]=1;}  
            printf("
");  
            printf("%d",n-ans.size());  
            for(int i=1;i<=n;i++) if(!vis[i]) printf(" %d",i);  
            printf("
");  
        }  
        return 0;  
    }  
    /* 
    2 
    5 
    3 4 5 0 
    1 3 5 0 
    2 1 4 5 0 
    2 3 5 0 
    1 2 3 4 0 
    5 
    2 3 5 0 
    1 4 5 3 0 
    1 2 5 0 
    1 2 3 0 
    4 3 2 1 0 
    */