[HOJ 102][POI 12 Stage 3] 成雙成對

這題是我去看官方解的圖才會的QAQ...覺得這解法太神奇了

作法：

首先要先發現，所有圖的最大的好感度都等於點數。所以問題轉化成要怎麼把一張圖分成兩個子圖，使得子圖內每個點的度都是偶數。

如果這世界上沒有奇點，那就作完了。

如果有奇點，叫他P好了，那麼考慮P和P的鄰居這個子圖，把所有的邊反過來(有改無，無改有)，然後把P砍掉，去作剩下的圖的答案，然後再看P要加入哪一組裡即可。

因為P的鄰居們一定是偶數個被分在一組，奇數個被分在另一組。然後因為P也要滿足條件，所以他等一下會被加到偶數個鄰居的那組。所以如果不把邊全部反過來的話，這時候偶數個鄰居的那組就不滿足條件了(他們的度都變成奇數)。所以如果考慮把子圖的邊反過來，這樣作完補圖之後會把原圖分成兩組，其中一組有偶數個P的鄰居，且除了P的鄰居以外的點的度都是偶數，另一組有奇數個P的鄰居的組裡每個點的度都是偶數，這樣把P加入偶數鄰居的組就OK了。

code :

#include<bits/stdc++.h>
using namespace std;
 
int n ;
bool G[201][201],now[201] ;
int gp[201] ;
 
void solve()
{
    vector<int> tmp ;
    int deg[201]={0} ;
    for(int i=1;i<=n;i++) if(now[i]) tmp.push_back(i) ;
    for(int i=1;i<=n;i++) if(now[i])
        for(int j=1;j<=n;j++) if(j!=i && now[j] && G[i][j])
        deg[i]++ ;
 
    bool ok=1 ;
    int st ;
    for(st=0;st<tmp.size();st++)
        if(deg[tmp[st]]%2) { ok=0 ; break ; }
    if(ok)
    {
        for(int i=0;i<tmp.size();i++) gp[tmp[i]]=1 ;
        return ;
    }
 
    for(int i=0;i<tmp.size();i++) if(i!=st && G[tmp[i]][tmp[st]])
        for(int j=0;j<tmp.size();j++) if(j!=i && j!=st && G[tmp[j]][tmp[st]])
        G[tmp[i]][tmp[j]]=(!G[tmp[i]][tmp[j]]) ;
    now[tmp[st]]=0 ;
    solve() ;
 
    int num1=0 ;
    for(int i=0;i<tmp.size();i++)
        if(i!=st && G[tmp[i]][tmp[st]] && gp[tmp[i]]==1)
        num1++ ;
    if(num1%2) gp[tmp[st]]=2 ;
    else gp[tmp[st]]=1 ;
}
 
main()
{
    scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        int m ; scanf("%d",&m) ;
        while(m--)
        {
            int x ; scanf("%d",&x) ;
            G[i][x]=1 ;
        }
    }
    for(int i=1;i<=n;i++) now[i]=1 ;
    solve() ;
    int num=0,cnt=0 ;
    for(int i=1;i<=n;i++) if(gp[i]==1) num++ ;
    printf("%d\n",num) ;
    for(int i=1;i<=n;i++) if(gp[i]==1) printf("%d%c",i,++cnt==num?'\n':' ') ;
}