概要:
进行拓扑排序是从入度为0的入手依次排序。
无等于条件排序
直接进行拓扑排序
含等于条件排序
先对等于条件进行并查集合并然后拓扑排序,且排序的时候注意存边时存的是父节点(需要Find一下)
模板:
vector建图
const int maxn = 3e4+10;
int deg[maxn];
vector<int>edge[maxn];
int f[maxn];
int n,m,cnt=0,tt=0;
void topo()
{
queue<int>q;
while(!q.empty())q.pop();
for(int i=0;i<n;++i){
if(!deg[i]){
q.push(i);
// --deg[i];
}
}
while(!q.empty()){
int now=q.top();q.pop();
// f[cnt]=now;++cnt;
for(auto i:edge[x]){
--deg[i];
if(!deg[i]){
q.push(i);
// --deg[i];
}
}
}
}
int main()
{
for(int i=0;i<n;++i){
deg[i]=0;
edge[i].clear();
}
string tmp1,tmp2;
for(int i=1;i<=m;++i){
cin>>tmp1>>tmp2;
edge[mt[tmp1]].push_back(mt[tmp2]);//建边tmp1->tmp2
++deg[mt[tmp2]];//tmp2的入度+1
}
topo();
}
}
领接矩阵建图
void topo()
{
queue<int>q;
for(int i=0;i<n;++i){
if(!deg[i]){
q.push(i);
--deg[i];
}
}
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<n;++i){
if(!mt[x][i]) continue;//无此边
--deg[i];
if(!deg[i]){
q.push(i);
--deg[i];
}
}
}
}
int main()
{
tt{
cin>>x>>y;
if(mt[x][y]) continue;
mt[x][y]=1;
++deg[y];
}
}
void topo()
{
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(mt[i][j]) ++deg[j];
}
}
for(int i=0;i<n;++i){
int k=1;
while(deg[i]!=0)++k;
ans[i]=k;
--deg[k];
for(int j=1;j<n;++j){
if(mt[k][j])
--deg[j];
}
}
}
原文链接: https://www.cnblogs.com/waryan/p/12844448.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/346940
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!