当前位置：首页 > ds >正文

【图论】拓扑排序

ds 2025/8/21 7:11:17

模板 B3644

BFS

const int N=2e5+10,mod=998244353,M=2e5+10;
int n,m;
vector<int>v[N],tp;
int din[N];
void toposort(){queue<int>q;forr(i,1,n)if(din[i]==0)q.push(i);while (q.size()){int x=q.front();tp.push_back(x);q.pop();for(auto i:v[x]){if(--din[i]==0)q.push(i);//把入度为0的点都放进q等待遍历}}
}
void solve(){cin>>n;forr(i,1,n){int a;while (cin>>a&&a){v[i].push_back(a);din[a]++;}}toposort();for(auto i:tp)cout<<i<<' ';
}

DFS

int n,m;
vector<int>v[N],tp;
int c[N];
void dfs(int x){c[x]=-1;//在路上的都赋值for(auto i:v[x]){if(c[i]==0)dfs(i);//进入还没走过的路径}c[x]=1;//走完的记录tp.push_back(x);return;
}
void toposort(){memset(c,0,sizeof c);forr(i,1,n){if(c[i]==0)dfs(i);for(auto i:tp)cout<<i<<' ';cout<<endl;}reverse(tp.begin(),tp.end());//dfs 先返回的是儿子节点 最后要逆转
}
void solve(){cin>>n;forr(i,1,n){int a;while (cin>>a&&a){v[i].push_back(a);}}toposort();for(auto i:tp)cout<<i<<' ';
}

把题意抽象成图

P4089

每个点只有一个出度

int n;
vector<int>tp;//存所有入度为0的点，不成环
int din[N],a[N];
void bfs(){queue<int>q;forr(i,1,n)if(din[i]==0)q.push(i);while (q.size()){int x=q.front();tp.push_back(x);q.pop();if(--din[a[x]]==0)q.push(a[x]);//把入度为0的点都放进q等待遍历}
}
void solve(){cin>>n;forr(i,1,n){cin>>a[i];din[a[i]]++;}bfs();cout<<n-tp.size()<<endl;
}

GDCPC 2024 不等式

const int N=2e5+10,mod=998244353,M=2e5+10;
struct pr
{int b,c;
};
int n,m;
int ans,sz;
set<int>v[N];
vector<pr>sm[N];
int din[N],val[N];void toposort(){queue<int>q;forr(i,1,n)if(!din[i])q.push(i);while (q.size()){int x=q.front();q.pop();sz++;for(auto i:v[x]){if(--din[i]==0)q.push(i);}val[x]=1;for(auto i:sm[x]){val[x]=max(val[x],val[i.b]+val[i.c]);}ans+=val[x];}}
void solve(){cin>>n>>m;forr(i,1,m){int x,y,z;cin>>x>>y>>z;sm[x].push_back({y,z});if(!v[y].count(x)){v[y].insert(x);din[x]++;}if(!v[z].count(x)){v[z].insert(x);din[x]++;}}toposort();cout<<(ans>1e9||sz<n?-1:ans)<<endl;
}

XJTUPC2024 雪中楼把题意抽象成图

抽象成一个链表，矮的后继高的
给的 $a_i$ 比 $i$ 矮， $ai→ia_i\rightarrow i$
指向相同前驱的点，编号越小越高，把树变链表

int n;
vector<int>v[N];
int a[N];
void bfs(){queue<int>q;forr(i,1,n)if(din[i]==0)q.push(i);while (q.size()){int x=q.front();tp.push_back(x);q.pop();if(--din[a[x]]==0)q.push(a[x]);//把入度为0的点都放进q等待遍历}
}
void solve(){cin>>n;forr(i,1,n){cin>>a[i];v[a[i]].push_back(i);//矮的指向高的}int nw=0;forr(i,1,n){//指向同一个点的 序号越小越高sort(v[nw].begin(),v[nw].end(),greater<int>());//z序号越小越高 序号从大到小while (v[nw].size()>1)//把高的都归位{int h=v[nw].back();v[nw].pop_back();int l=v[nw].back();v[l].push_back(h);}nw=v[nw].front();}nw=0;forr(i,1,n){if(v[nw].size()){cout<<v[nw].front()<<' ';nw=v[nw].front();}}}

带权值遍历DAG

P1038 神经网络

const int N=110,mod=998244353,M=2e5+10;
int n,m;
vector<int>v[N],e[N];
int din[N],dout[N],w[N][N],u[N],c[N];void toposort(){queue<int>q;forr(i,1,n)if(!din[i])q.push(i);while (q.size()){int x=q.front();q.pop();int sm=0;for(auto j:v[x]){if(c[x]>0)c[j]+=w[x][j]*c[x];if(!--din[j])q.push(j);}}
}
void solve(){cin>>n>>m;forr(i,1,n){cin>>c[i]>>u[i];if(c[i]==0)c[i]-=u[i];}forr(i,1,m){int x,y,wv;cin>>x>>y>>wv;w[x][y]=wv;v[x].push_back(y);din[y]++,dout[x]++;}toposort();int fg=0;forr(i,1,n){if(!dout[i]&&c[i]>0)cout<<i<<' '<<c[i]<<endl,fg=1;}if(!fg)cout<<"NULL"<<endl;
}