RT

代码如下

#include<iostream>
#include<cstdio>
#define NUM 1510
#define FOR(a,b,c) for( int a = b;a <= c;a++ )
using namespace std;

int n;

struct bian { //边
	int next, to;
};
bian e[NUM << 4];
int head[NUM];
int cnt;

void add( int x, int y ) {
	e[++cnt].next = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
int tou = 0x7f7f7f;//记录树根
int ling;//零(ling 表示白色节点的数量)
int yi;//一(yi 表示黑色节点的数量)
bool v[NUM];

void dfs( int p, int now ) {
	if ( v[p] ) return; //防止多次访问同一个点
	v[p] = 1;
	if ( now ) yi++;
	else ling++;
	for ( int i = head[p]; i; i = e[i].next ) {
		int to = e[i].to;
		dfs( to, now ^ 1 );
	}
}

int main() {

	cin >> n;
	FOR( i, 1, n ) {
		int x, y, z;
		cin >> x >> y;
		tou = min(tou, x); //用编号最小的点当做树根
		FOR( j, 1, y ) { //无向边
			cin >> z;
			add( x, z );
			add( z, x );
		}
	}
	dfs( tou, 0 ); //黑白染色
	cout << min( ling, yi ); //取黑或取白

	return 0;
}