### P1983 station classification (topological sorting)

wx6110fa547fd20 2021-08-10 07:39:18 阅读数:947

p1983 station classification topological sorting
P1983 Station classification ( A topological sort )

Portal

Ideas ： Abstract the relationship of each train number and station into the relationship of edges , The level of non stopping station must be lower than that of stopping station , So you can create an edge , Then just do it with topological sorting , Pay attention to the judgment of heavy edges .

``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;
#define mst(a) memset(a,0,sizeof a)
int n,m,in[N],vis[N],a[N];
bool edge[N][N];
vector<int>e[N];
int toposort(){
queue<pair<int,int> >q;
int ans=1;
for(int i=1;i<=n;i++) if(!in[i]) q.push({i,1});
while(q.size()){
int u=q.front().first;
int g=q.front().second;
q.pop();
for(auto v:e[u]){
in[v]--;
if(!in[v]) q.push({v,g+1}),ans=max(ans,g+1);// Maximum level found .
}
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,cnt;i<=m;i++){
scanf("%d",&cnt);
mst(vis);
for(int j=1;j<=cnt;j++)
scanf("%d",&a[j]),vis[a[j]]=1;
for(int j=a[1];j<=a[cnt];j++)
if(!vis[j])
for(int k=1;k<=cnt;k++)
if(!edge[j][a[k]]) edge[j][a[k]]=1,e[j].push_back(a[k]),in[a[k]]++;
}
printf("%d\n",toposort());
return 0;
}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
```