模拟 + 染色 玄关

#include<bits/stdc++.h>
using namespace std;
int b,n,ans1[105],ans2[105],l1,l2,no[105],num;
bool f[105][105],vis[105],fi,know[105][105];
vector <int> fa[105];
short int m[105];
void dfs(int v,short int c)//染色
{
    m[v] = c;
    if(c == 1) ans1[++ l1] = v;
    else ans2[++ l2] = v;
    for(int i = 1;i <= n;i ++)
    {
        if(f[v][i])
        {
            if(m[i] == c)
            {
                fi = 1;
                return;
            }
            if(!m[i]) dfs(i,3 - c);
            if(fi) return;
        }
    }
    return;
}
bool cl1(int u)//查找是否可以呆在这一组
{
    bool v = 1;
    for(int i = 1;i <= l2;i ++)
    {
        if(!know[ans2[i]][u] || !know[u][ans2[i]])
        {
            v = 0;
            break;
        }
    }
    return v;
}
bool cl2(int u)//同上
{
    bool v = 1;
    for(int i = 1;i <= l2;i ++)
    {
        if(!know[ans2[i]][u] || !know[u][ans2[i]])
        {
            v = 0;
            break;
        }
    }
    return v;
}
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        cin >> b;
        while(b)
        {
            if(f[b][i] == 1) f[b][i] = 0,know[b][i] = know[i][b] = 1;
            else f[i][b] = 1;//打标记
            cin >> b;
        }
    }
    for(int i = 1;i <= n;i ++)//对于不能分在同一组的进行染色
        for(int j = 1;j <= n;j ++)
            if(f[i][j]) fa[j].push_back(i);
    for(int i = 1;i <= n;i ++)
    {
        if(!vis[i])
        {
            int c = 0;
            for(int j = 0;j < fa[i].size();j ++)
            {
                int u = fa[i][j];
                if(m[u])
                {
                    if(c == 0) c = 3 - m[u];
                    else if(c == m[u])//不满足条件
                    {
                        cout << "No solution\n";
                        return 0;
                    }
                }
            }
            if(!c)
            {
                for(int j = 1;j < i;j ++)
                {
                    if(f[i][j] && m[j])
                    {
                        if(c == m[j])
                        {
                            cout << "No solution\n";
                            return 0;
                        }
                        else c = 3 - m[j];
                    }
                }
                if(!c)
                {
                    c = 1;
                    if(i != 1)
                    {
                        no[++ num] = i;
                        continue;
                    }
                }
            }
            for(int j = 0;j < fa[i].size();j ++)
            {
                int u = fa[i][j];
                if(!m[u]) m[u] = 3 - c;
            }
            dfs(i,c);
        }
        if(fi)
        {
            cout << "No solution\n";
            return 0;
        }
    }
    for(int k = 1;k <= num;k ++)
    {
        int u = no[k];
        if(l1 > l2)//没有被分配的
        {
            if(cl2(u))
            {
                ans2[++ l2] = u;
                continue;
            }
            else if(cl1(u))
            {
                ans1[++ l1] = u;
                continue;
            }
        }
        else
        {
            if(cl1(u))
            {
                ans2[++ l1] = u;
                continue;
            }
            else if(cl2(u))
            {
                ans1[++ l2] = u;
                continue;
            }
        }
        cout << "No solution\n";
        return 0;
    }
    sort(ans1 + 1,ans1 + 1 + l1);//从小到大
    sort(ans2 + 1,ans2 + 1 + l2);
    printf("%d ",l1);
    for(int i = 1;i <= l1;i ++) printf("%d ",ans1[i]);
    printf("\n%d ",l2);
    for(int i = 1;i <= l2;i ++) printf("%d ",ans2[i]);
    printf("\n");
    return 0;
}