b333.
NOIP2013 4.车站分级
內容
一条单向的铁路线上，依次有编号为 1, 2, …, n的n个火车站。每个火车站都有一个级别，最低为1级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）
例如，下表是5趟车次的运行情况。其中，前4趟车次均满足要求，而第 5趟车次由于停靠了3号火车站（2 级）却未停靠途经的 6号火车站（亦为 2 级）而不满足要求。
现有m趟车次的运行情况（全部满足要求） ，试推算这 n 个火车站至少分为几个不同的级别。
輸入說明
第一行包含2个正整数 n, m，用一个空格隔开。
第 i + 1 行（1 ≤ i ≤ m）中，首先是一个正整数 si（2 ≤ si ≤ n），表示第i趟车次有 si个停靠站；接下来有si个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。
第 i + 1 行（1 ≤ i ≤ m）中，首先是一个正整数 si（2 ≤ si ≤ n），表示第i趟车次有 si个停靠站；接下来有si个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。
輸出說明
输出只有一行，包含一个正整数，即 n 个火车站最少划分的级别数。
範例輸入
#1
【输入样例 1】 9 2 4 1 3 5 6 3 3 5 6 【输入样例 2】 9 3 4 1 3 5 6 3 3 5 6 3 1 5 9
範例輸出
#1
【输出样例 1】 2 【输出样例 2】 3
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
提示 ：
对于20%的数据，1 ≤ n, m ≤ 10；
对于50%的数据，1 ≤ n, m ≤ 100；
对于100%的数据，1 ≤ n, m ≤ 1000。
对于50%的数据，1 ≤ n, m ≤ 100；
对于100%的数据，1 ≤ n, m ≤ 1000。
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||