codeforces Gargari and Permutations(DAG+BFS)

/*
     题意：求出多个全排列的lcs！
     思路：因为是全排列，所以每一行的每一个数字都不会重复，所以如果有每一个全排列的数字 i 都在数字 j的前面，那么i， j建立一条有向边！
      最后用bfs遍历整个图，求出源点到每一个点的距离，其中最大的距离就是最长的公共子序列的长度！
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define N 1005

using namespace std;
vector<int>g[N];
queue<int>q;
int pos[6][N];
int d[N];
int vis[N];
int n, k;
int ans;

bool judge(int a, int b){//保证数字a 在数字 b的前边
    for(int i=1;  i<=k; ++i)
        if(pos[i][a] > pos[i][b])
            return false;
    return true;
}

void bfs(int x){
    q.push(x);
    ans=0;
    vis[0]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();    
        vis[u]=0;
        ans=max(ans, d[u]);
        int len=g[u].size();
        for(int i=0; i<len; ++i){
            int v=g[u][i];
            if(d[v]<d[u]+1){
                d[v]=d[u]+1;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}

int main(){
    while(scanf("%d%d", &n, &k)!=EOF){
        for(int i=1; i<=k; ++i)
            for(int j=1; j<=n; ++j){
                int x;
                scanf("%d", &x);
                pos[i][x]=j;
            }
        for(int i=1; i<=n; ++i){
            d[i]=0;//初始化所有点到源点的距离都为最小（因为是求最大距离，不是最短距离）
            vis[i]=0;
            g[0].push_back(i);
            for(int j=i+1; j<=n; ++j)
                if(judge(i, j))
                   g[i].push_back(j);
                else if(judge(j, i))
                   g[j].push_back(i);
        }
        bfs(0);
        printf("%d\n", ans);
        for(int i=0; i<=n; ++i)//不要忘记将vector清空
            g[i].clear();
    }
    return 0;
}