天津做网站的企业,各地城乡建设网站更新,移动互联网应用软件开发,68网页设计欣赏题4#xff1a;车站分级
【题目描述】
一条单向的铁路线上#xff0c;依次有编号为 1 , 2 , … , n 1,2,…,n 1,2,…,n 的 n n n 个火车站。每个火车站都有一个级别#xff0c;最低为 1 1 1 级。现有若干趟车次在这条线路上行驶#xff0c;每一趟都满足如下要求#…题4车站分级
【题目描述】
一条单向的铁路线上依次有编号为 1 , 2 , … , n 1,2,…,n 1,2,…,n 的 n n n 个火车站。每个火车站都有一个级别最低为 1 1 1 级。现有若干趟车次在这条线路上行驶每一趟都满足如下要求如果这趟车次停靠了火车站 x x x则始发站、终点站之间所有级别大于等于火车站 x x x 的都必须停靠。注意起始站和终点站自然也算作事先已知需要停靠的站点
例如下表是 5 5 5 趟车次的运行情况。其中前 4 4 4 趟车次均满足要求而第 5 5 5 趟车次由于停靠了 3 3 3 号火车站 2 2 2 级却未停靠途经的 6 6 6 号火车站亦为 2 2 2 级而不满足要求。 现有 m m m 趟车次的运行情况全部满足要求试推算这 n n n 个火车站至少分为几个不同的级别。
【输入文件】
第一行包含 2 2 2 个正整数 n , m n,m n,m用一个空格隔开。
第 i 1 i1 i1 行 1 ≤ i ≤ m 1≤i≤m 1≤i≤m中首先是一个正整数 s i 2 ≤ s i ≤ n si2≤s_i≤n si2≤si≤n表示第 i i i 趟车次有 s i s_i si 个停靠站接下来有 s i s_i si 个正整数表示所有停靠站的编号从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。
【输出文件】
输出只有一行包含一个正整数即 n n n 个火车站最少划分的级别数。
【输入样例1】
9 2 4 1 3 5 6 3 3 5 6
【输出样例1】
2
【输入样例2】
9 3 4 1 3 5 6 3 3 5 6 3 1 5 9
【输出样例2】
3
【数据范围】
对于 20 % 20\% 20% 的数据 1 ≤ n , m ≤ 10 1≤n,m≤10 1≤n,m≤10
对于 50 % 50\% 50% 的数据 1 ≤ n , m ≤ 100 1≤n,m≤100 1≤n,m≤100
对于 100 % 100\% 100% 的数据 1 ≤ n , m ≤ 1000 1≤n,m≤1000 1≤n,m≤1000。
【代码如下】
#include bits/stdc.h
using namespace std;
ifstream cin(level.in);
ofstream cout(level.out);
struct cs {int to, next;
} a[1000001];
int b[1001], f[1001], head[1001];
bool vi[1001][1001];
int n, m, x, y, z, ans, ll;
void init(int x, int y) {a[ll].to y;a[ll].next head[x];head[x] ll;
}
int dfs(int x) {for (int k head[x]; k; k a[k].next)if (!f[a[k].to])f[x] max(f[x], dfs(a[k].to));elsef[x] max(f[x], f[a[k].to]);return f[x];
}
int main() {cin n m;for (int i 1; i m; i) {cin z;for (int i 1; i z; i) cin b[i];int l 1;for (int i b[1]; i b[z]; i) {if (b[l] i) {l;continue;} else {for (int k 1; k z; k) {if (!vi[b[k]][i]) {init(b[k], i);vi[b[k]][i] 1;}}}}}for (int i 1; i n; i) {if (!f[i]) {ans max(ans, dfs(i));}}cout ans;
}
