topsort

``` 首先是有向无环图 有先后顺序进行排序 以上面给课程排序为例，我们首先要学的，一定是一个不需要任何预备知识的课程，然后学完这个课程之后，根据边的关系再看有哪些新的课程可以学习，同时我们还要清楚，学完一门课程后，就不需要再次学习这一门课程了。 我们将其与图做个类比。 不需要预备知识的课程-> 入度为0的点 新的课程->所指向的下一个点 每门课之学一次->从图中删除节点 && 从图中删除有向边 接着再根据图类比结果决定存储的数据 入度为0的点->需要存储每个节点的入度 所指向的下一个点->需要存每个节点的后继 删除节点与有向边-> 这里讨论一下： 如果我们真的删除了节点和有向边，那就意味着无法在找到这些数据了。因为我们还需要判断是否形成了DAG，最保险的做法是将下一个节点的入度-1。如果发现某个节点的入度为-1了，表明存在有向环，那么说明不存在与拓扑排序。 #include<bits/stdc++.h> using namespace std; const int N=100010; int head[N]; struct edg{ int next,to; }a[N]; int cnt; typedef long long ll; int indegree[N]; queue<int>q; void add(int x,int y) { a[++cnt].to=y; a[cnt].next=head[x]; head[x]=cnt; } char str[N]; string s[N]; string ans; int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",str); s[i]=str; } for(int i=1;i<n;i++) { int flag=0; int len=min(s[i].length(),s[i+1].length()); for(int j=0;j<len;j++) if(s[i][j]!=s[i+1][j]){ add(s[i][j],s[i+1][j]); indegree[s[i+1][j]]++; flag=1; break; } if(!flag) if(s[i].length() > s[i + 1].length()) { puts("Impossible"); return 0;} } for(int i='a';i<='z';i++) if(!indegree[i])q.push(i); while(!q.empty()) { int u=q.front();q.pop(); ans += u; for(int i=head[u];i;i=a[i].next) { int v=a[i].to; indegree[v]--; if(indegree[v]==0)q.push(v); } } if(ans.length() != 26) puts("Impossible"); else cout << ans; } ```