PAT (Advanced Level) Practice 1146 Topological Order (25分)
PAT (Advanced Level) Practice 1146 Topological Order (25分)
1146 Topological Order (25分)
This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test each of the options.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 1,000), the number of vertices in the graph, and M (≤ 10,000), the number of directed edges. Then M lines follow, each gives the start and the end vertices of an edge. The vertices are numbered from 1 to N. After the graph, there is another positive integer K (≤ 100). Then K lines of query follow, each gives a permutation of all the vertices. All the numbers in a line are separated by a space.
Output Specification:
Print in a line all the indices of queries which correspond to "NOT a topological order". The indices start from zero. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line. It is graranteed that there is at least one answer.
Sample Input:
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6Sample Output:
3 4思路：数据结构都教过的题目啦，检验一个序列是否为拓扑序，模拟即可，连边入度-1，看下一个是不是入度为0
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
template <typename T> inline void read(T& x)
{
x=0;char ch=getchar();ll f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
/*
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6 */
ll n,m,head[1005],cnt,test[1005],rudu[1005],testrudu[1005];
vector<ll>ans;
struct node
{
ll to,next;
}edge[10005];
inline void add(ll u,ll v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
rudu[v]++;
}
inline void init()
{
for(rg j=1;j<=n;j++)testrudu[j]=rudu[j];
}
int main()
{
memset(head,-1,sizeof(head));
cin>>n>>m;
for(rg i=1;i<=m;i++)
{
ll a,b;
cin>>a>>b;
add(a,b);
}
ll k;
cin>>k;
//cout<<k<<endl;
/* for(rg i=1;i<=n;i++)cout<<rudu[i]<<" ";
cout<<endl; */
for(rg i=1;i<=k;i++)
{
for(rg j=1;j<=n;j++)cin>>test[j];
init();
rg j;
for(j=1;j<=n;j++)
{
/* for(rg i=1;i<=n;i++)cout<<testrudu[i]<<" ";
cout<<endl; */
if(!testrudu[test[j]])
{
for(rg m=head[test[j]];~m;m=edge[m].next)
{
ll to=edge[m].to;
testrudu[to]--;
}
}
else break;
}
if(j<=n)ans.push_back(i-1);
}
ll cnt=0;
//cout<<ans.size()<<endl;
for(auto it:ans)
{
cnt++;
cnt==ans.size()?cout<<it<<endl:cout<<it<<" ";
}
// while(1)getchar();
return 0;
}腾讯云开发者
