Topological Order

PAT-1146

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdio>

#include<sstream>

#include<set>

#include<map>

#include<cmath>

#include<vector>

#include<unordered_map>

using namespace std;

int n,m;

const int maxn=1003;

const int maxm=10004;

int ma[maxn][maxn];

int temp[maxn];

int main(){

	cin>>n>>m;

	memset(ma,-1,sizeof(ma));

	for(int i=0;i<m;i++){

		int from,to;

		cin>>from>>to;

		ma[from][to]=1;

		ma[from][from]=0;

		ma[to][to]=0;

	}

	int k;

	cin>>k;

	vector<int>ve;

	for(int i=0;i<k;i++){

		for(int j=0;j<n;j++){

			cin>>temp[j];

		}

		bool flag=true;

		for(int j=0;j<n;j++){

			for(int t=0;t<j;t++){

				if(ma[temp[j]][temp[t]]==1){

					flag=false;

					break;

				}

			}

			if(!flag)

				break;

		}

		if(!flag){

			ve.push_back(i);

		}

	}

	for(int i=0;i<ve.size();i++){

		if(i==(int)ve.size()-1){

			cout<<ve[i]<<endl;

		}else{

			cout<<ve[i]<<" ";

		}

	}

	return 0;

}

巴特西

PAT-1146（Topological Order）拓扑排序+判断一个序列是否满足拓扑序列

Topological Order

PAT-1146

最新文章

热门文章