A题二分图判定。既然要父母颜色不同,那就在父母间连一条边,子女什么的就不管了。

const int mx = 105;

vector<int> g[mx];
bool vis[mx], color[mx], ok;

class Family
{
    public:
        void dfs(int v)
        {
            vis[v] = true;
            int i, w;
            For(i, g[v].size())
            {
                if (!ok) return;
                w = g[v][i];
                if (!vis[w])
                {
                    color[w] = !color[v];
                    dfs(w);
                }
                else if (color[w] == color[v])
                {
                    ok = false;
                    return;
                }
            }
        }

        void checkTwoColor(int n) /// n为图的顶点数
     {
            ok = true;
            int i;
            For(i, n) if (!vis[i]) dfs(i);
        }

        string isFamily(vector<int> p1, vector<int> p2)
        {
            int i, n = p1.size();
            For(i, n) if (~p1[i]) g[p1[i]].PB(p2[i]), g[p2[i]].PB(p1[i]); /// 既然要父母颜色不同,那就在父母间连一条边,子女什么的就不管了
         checkTwoColor(n);
            return ok ? "Possible" : "Impossible";
        }
};

Comments

comments powered by Disqus