【题目描述】

众所周知，大学里有许多不同的专业，但冗杂的专业造成了一个严重的问题：究竟哪个大学更好？

现提出一个新概念，使得此问题能够部分解决。举一个例子：

假设有三所大学：X大学、Y大学、Z大学，每所大学都有三个专业：A、B、C，而这三所大学三个专业的公认排名如下：

(1)A专业排名：X > Y > Z；

(2)B专业排名：X > Z > Y；

(3)C专业排名：Z > X > Y；

显然，X大学所有的专业比Y大学的排名都要靠前，所以X大学一定比Y大学好，运用新概念，我们就能够部分比较出一些大学的优劣。

给定一份完整的各所大学不同专业排名，需要找出K所大学(U₁、U₂、U₃、······、U_k)，U_i大学一定比U_j大学(i < j)好，询问K的最大值是多少。

【输入描述】

第一行输入两个整数N、M(0 < N,M ≤ 100)，表示大学数目和专业数目；

接下来M行，每行输入N所大学的编号U_j，表示对于第i个专业，N所大学的排名。

【输出描述】

输出一个数，表示答案。

【样例输入】

3 3

1 2 3

1 3 2

3 1 2

【样例输出】

2

源代码：#include
       
        #include
        
         #include
         
          using namespace std;int m,n,Num(0),Ans(0),f[101],In[101],Head[101],i[101][101];struct Node{    int To,Next;}Edge[10001];void Add(int t1,int t2) //边表。{    Edge[++Num].To=t2;    Edge[Num].Next=Head[t1];    Head[t1]=Num;}int DFS(int t) //树形DP找最长链。{    if (!Head[t]) //孤独。      return 1;    if (f[t]!=-1) //链链衔接，一个重要的剪枝。      return f[t];    for (int a=Head[t];a;a=Edge[a].Next)      f[t]=max(f[t],DFS(Edge[a].To)+1);    return f[t]; //f[t]表示该节点最长链的长度。}int main() //其实去掉那些琐碎的东西，得到的就是核心问题。{    memset(f,-1,sizeof(f));    scanf("%d%d",&n,&m);    for (int a=1;a<=m;a++)      for (int b=1;b<=n;b++)      {        int t;        scanf("%d",&t);        i[t][a]=b; //i[a][b]表示在第a个专业方面，第b所大学的排名。      }    for (int a=1;a<=n;a++)      for (int b=1;b<=n;b++) //纯枚举。        if (a!=b)        {            bool Flag(0);            for (int c=1;c<=m;c++)              if (i[a][c]>i[b][c])              {                Flag=true;                break;              }            if (!Flag) //a大学比b大学一定强。            {                Add(a,b); //建立一条有向边。                In[b]++; //入度。            }        }    for (int a=1;a<=n;a++)      if (!In[a])        Ans=max(Ans,DFS(a));    printf("%d",Ans);    return 0;}