YZOJ P2966 染色
时间限制：2000MS 内存限制：131072KB
难度：\(7.0\)
-
题目描述
你有 \(n\) 只猫，每一只猫认识另一些猫。但若 \(a\) 猫认识 \(b\) 猫，\(b\) 猫不一定会认识 \(a\) 猫。
现在，你需要将每一只猫染成红色或绿色。你是否可以通过染色让每一只猫都认识偶数只和自己同色的猫呢？
-
输入格式
第一行 \(n\)；
接下来 \(n\) 行，每行第一个数 \(d_i\) 表示猫 \(i\) 认识的猫的个数，后面跟着 \(d_i\) 个数表示认识的猫是哪些。
-
输出格式
达不到要求，输出 Impossible。
否则第一行输出红色猫的个数，第二行输出哪些猫是红色（那么其他猫就是绿色）
可以输出任意方案。
-
样例输入
|
1 2 3 4 5 6 |
5 3 2 3 4 2 1 3 4 2 1 4 5 2 1 3 1 3 |
-
样例输出
|
1 2 |
3 1 2 3 |
-
数据规模与约定
对于 \(100\%\) 的数据，\(n \leq 2000\) 。
高斯消元是 \(O(n^3)\) 的，套个 std::bitset 就可以 \(\O(\frac{n^2}{32})) 。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <bitset> inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } std::bitset<2002>a[2001]; int main() { register int N=getnum(); for(register int i=1;i<=N;i++) { register int d=getnum(); if(d&1) a[i][i]=a[i][N+1]=true; for(register int j=1;j<=d;j++) a[i][getnum()]=true; } for(register int i=1;i<=N;i++) { register int j=i; while(j<=N && !a[j][i]) j++; if(j>N) continue; if(j!=i) a[i]^=a[j]^=a[i]^=a[j]; for(j=i+1;j<=N;j++) if(a[j][i]) a[j]^=a[i]; } for(register int i=N;i>1;i--) if(a[i][N+1]) { if(!a[i][i]) { printf("Impossible\n"); return 0; } for(register int j=i-1;j>=1;j--) if(a[j][i]) a[j]^=a[i]; } register int cnt=0; for(register int i=1;i<=N;i++) if(a[i][N+1]) cnt++; printf("%d\n",cnt); for(register int i=1;i<=N;i++) if(a[i][N+1]) printf("%d ",i); printf("\n"); return 0; } |