YZOJ P2966 染色

YZOJ P2966 染色

时间限制:2000MS      内存限制:131072KB

难度:\(7.0\)

  • 题目描述

你有 \(n\) 只猫,每一只猫认识另一些猫。但若 \(a\) 猫认识 \(b\) 猫,\(b\) 猫不一定会认识 \(a\) 猫。

现在,你需要将每一只猫染成红色或绿色。你是否可以通过染色让每一只猫都认识偶数只和自己同色的猫呢?

  • 输入格式

第一行 \(n\);

接下来 \(n\) 行,每行第一个数 \(d_i\) 表示猫 \(i\) 认识的猫的个数,后面跟着 \(d_i\) 个数表示认识的猫是哪些。

  • 输出格式

达不到要求,输出 Impossible

否则第一行输出红色猫的个数,第二行输出哪些猫是红色(那么其他猫就是绿色)

可以输出任意方案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据,\(n \leq 2000\) 。

 

 

 


 

 

 

 

高斯消元是 \(O(n^3)\) 的,套个 std::bitset  就可以 \(\O(\frac{n^2}{32})) 。

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注