1 /* 2      题意：求出多个全排列的lcs！ 3      思路：因为是全排列，所以每一行的每一个数字都不会重复，所以如果有每一个全排列的数字 i 都在数字 j的前面，那么i， j建立一条有向边！ 4       最后用bfs遍历整个图，求出源点到每一个点的距离，其中最大的距离就是最长的公共子序列的长度！ 5 */ 6 #include<iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<algorithm>10 #include<queue>11 #include<vector>12 #define N 100513 14 using namespace std;15 vector<int>g[N];16 queue<int>q;17 int pos[6][N];18 int d[N];19 int vis[N];20 int n, k;21 int ans;22 23 bool judge(int a, int b){//保证数字a 在数字 b的前边24     for(int i=1;  i<=k; ++i)25         if(pos[i][a] > pos[i][b])26             return false;27     return true;28 }29 30 void bfs(int x){31     q.push(x);32     ans=0;33     vis[0]=1;34     while(!q.empty()){35         int u=q.front();36         q.pop();    37         vis[u]=0;38         ans=max(ans, d[u]);39         int len=g[u].size();40         for(int i=0; i<len; ++i){41             int v=g[u][i];42             if(d[v]<d[u]+1){43                 d[v]=d[u]+1;44                 if(!vis[v]){45                     q.push(v);46                     vis[v]=1;47                 }48             }49         }50     }51 }52 53 int main(){54     while(scanf("%d%d", &n, &k)!=EOF){55         for(int i=1; i<=k; ++i)56             for(int j=1; j<=n; ++j){57                 int x;58                 scanf("%d", &x);59                 pos[i][x]=j;60             }61         for(int i=1; i<=n; ++i){62             d[i]=0;//初始化所有点到源点的距离都为最小（因为是求最大距离，不是最短距离）63             vis[i]=0;64             g[0].push_back(i);65             for(int j=i+1; j<=n; ++j)66                 if(judge(i, j))67                    g[i].push_back(j);68                 else if(judge(j, i))69                    g[j].push_back(i);70         }71         bfs(0);72         printf("%d\n", ans);73         for(int i=0; i<=n; ++i)//不要忘记将vector清空74             g[i].clear();75     }76     return 0;77 }