3116 問題 P: 打擊犯罪(black)
時間限制: 1s
內(nèi)存限制: 128MB 提交: 25 解決: 7
題目描述
某個地區(qū)有n(n<=1000)個犯罪團(tuán)伙,當(dāng)?shù)鼐桨凑账麄兊奈kU程度由高到低給他們編號為1-n,他們有些團(tuán)伙之間有直接聯(lián)系,但是任意兩個團(tuán)伙都可以通過直接或間接的方式聯(lián)系,這樣這里就形成了一個龐大的犯罪集團(tuán),犯罪集團(tuán)的危險程度由集團(tuán)內(nèi)的犯罪團(tuán)伙數(shù)量唯一確定,而與單個犯罪團(tuán)伙的危險程度無關(guān)(該犯罪集團(tuán)的危險程度為n)?,F(xiàn)在當(dāng)?shù)鼐较MūM量少的時間(即打擊掉盡量少的團(tuán)伙),使得龐大的犯罪集團(tuán)分離成若干個較小的集團(tuán),并且他們中最大的一個的危險程度不超過n/2。為達(dá)到最好的效果,他們將按順序打擊掉編號1到k的犯罪團(tuán)伙,請編程求出k的最小值。
輸入
第一行一個正整數(shù)n。接下來的n行每行有若干個正整數(shù),第一個整數(shù)表示該行除第一個外還有多少個整數(shù),若第i行存在正整數(shù)k,表示i,k兩個團(tuán)伙可以直接聯(lián)系。
樣例輸入
7
2 2 5
3 1 3 4
2 2 4
2 2 3
3 1 6 7
2 5 7
2 5 6
提示
【提示】
輸出1(打擊掉犯罪團(tuán)伙)