
 0通过
 33提交
 题目提供者 洛谷
 评测方式 云端评测
 标签 2SAT 构造 POI 2011 高性能
 难度 尚无评定
 时空限制 1000ms / 512MB
最新讨论 显示
题目描述
Hostile Bitotia launched a sneak attack on Byteotia and occupied a significant part of its territory.
The King of Byteotia, Byteasar, intends to organise resistance movement in the occupied area.
Byteasar naturally started with selecting the people who will form the skeleton of the movement.
They are to be partitioned into two groups:
the conspirators who will operate directly in the occupied territory, and the support group that will operate inside free Byteotia.
There is however one issue  the partition has to satisfy the following conditions:
Every pair of people from the support group have to know each other  this will make the whole group cooperative and efficient.
The conspirators must not know each other.
None of the groups may be empty, i.e., there has to be at least one conspirator and at least one person in the support group.
Byteasar wonders how many ways there are of partitioning selected people into the two groups.
And most of all, whether such partition is possible at all.
As he has absolutely no idea how to approach this problem, he asks you for help.
给定一张无向图，要求你把图中的每个点染成红色或蓝色，使得红色的点形成一个团，蓝色的点形成一个独立集
输入输出格式
输入格式：The first line of the standard input holds one integer $n$ ($2\le n\le 5000$), denoting the number of people engaged in forming the resistance movement.
These people are numbered from 1 to $n$ (for the sake of conspiracy!).
The $n$ lines that follow describe who knows who in the group.
The $i$th of these lines describes the acquaintances of the person $i$ with a sequence of integers separated by single spaces.
The first of those numbers, $k_i$ ($0\le k_i\le n1$), denotes the number of acquaintances of the person $i$.
Next in the line there are $k_i$ integers $a_{i,1},a_{i,2},\cdots,a_{i,k_i}$  the numbers of $i$'s acquaintances.The numbers $a_{i,j}$ are given in increasing order and satisfy $1\le a_{i,j}\le n$,$a_{i,j}\ne i$. You may assume that if $x$ occurs in the sequence $a_i$ (i.e., among $i$'s acquaintances), then also $i$ occurs in the sequence $a_x$(i.e., among $x$'s acquaintances).
输出格式：In the first and only line of the standard output your program should print out one integer:
the number of ways to partition selected people into the conspirators and the support group.
If there is no partition satisfying aforementioned conditions, then 0 is obviously the right answer.
输入输出样例
说明
给定一张无向图，要求你把图中的每个点染成红色或蓝色，使得红色的点形成一个团，蓝色的点形成一个独立集