1139: 车站分级

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：13 Solved：7

Description

一条单向的铁路线上，依次有编号为1, 2,..., n的n个火车站。每个火车站都有一个级别，最低为1级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站x，则始发站、终点站之间所有级别大于等于火车站x的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）
例如，下表是5趟车次的运行情况。其中，前4趟车次均满足要求，而第5趟车次由于停靠了3号火车站（2级）却未停靠途经的6号火车站（亦为2级）而不满足要求。


现有m趟车次的运行情况（全部满足要求），试推算这n个火车站至少分为几个不同的级别。



Input

每组输入数据的第一行包含2个正整数n, m，用一个空格隔开。
第i+1行（1≤i≤m）中，首先是一个正整数si（2≤si≤n），表示第i趟车次有si个停靠站；接下来有si个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。


数据规模：
对于20%的数据，1≤n, m≤10；
对于50%的数据，1≤n, m≤100；
对于100%的数据，1≤n, m≤1000。


Output

每组输出只有一行，包含一个正整数，即n个火车站最少划分的级别数。


Sample Input Copy 

9 2
4 1 3 5 6
3 3 5 6

Sample Output Copy 

2

HINT

样例2
9 3
4 1 3 5 6
3 3 5 6
3 1 5 9

3




#include<bits/stdc++.h>
using namespace std; 
int n,m,ans,a[2003],s,i,j,u,to[2003][2003],uans[2003],sto[2003];
void dfs(int u){
    if (uans) return;
    for(int i=1;i<=to[0];i++){
        if(!uans[to[i]]) dfs(to[i]);
        uans=max(uans,uans[to[i]]+1);
    }
    if(u>n) uans--;
    ans=max(ans,uans);
}
int main(){
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%d",&s);
        for (j=1;j<=s;j++) scanf("%d",&a[j]),sto[a[j]]=i,to[n+i][++to[n+i][0]]=a[j];
        for (u=a[1]+1;u<a;u++) 
            if (sto!=i) to[++to[0]]=n+i;    
    }
    for (i=1;i<=n;i++) 
        if (!uans[i]) dfs(i);
    printf("%d",++ans);
    return 0;
}

Source/Category

SubmitSubmit RecordStatisticsShowOff!