題目鏈接：點擊查看

題目大意：給出一棵有根樹，樹邊都是有向邊，再給出 $k$ 個關系 $(x,y)$，其意義是訪問完點 $x$ 后需要立即訪問點 $y$，問是否存在一種合適的拓撲序

題目分析：因為題目說明了 $k$ 個關系實際上也是一種綁定關系，在訪問點 $x$ 后需要立即訪問點 $y$，所以不妨直接將點 $y$ 與點 $x$ 合并在一起，更具體的說，可以將 $x$ 和 $y$ 進行縮點，然后對縮點后的圖進行拓撲，稍微畫一下樣例的圖就能明白了：



剩下的注意一下細節直接實現就可以了，需要注意的是，$k$ 個關系可能會組成環，這些都是需要特判的

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int p[N],f[N],nt[N],c[N],ord[N],ban[N],du[N],id;vector<int>node[N],dcc[N],ans;int find(int x) {return f[x]==x?x:f[x]=find(f[x]); }void merge(int x,int y)//y->x {int xx=find(x),yy=find(y);if(xx!=yy)f[yy]=xx; }int topo(int st) {int cnt=0;queue<int>q;q.push(st);while(q.size()){int u=q.front();q.pop();cnt++;for(auto it:dcc[u])ans.push_back(it);for(auto v:node[u])if(--du[v]==0)q.push(v);}return cnt; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m,rt;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",p+i);if(p[i]==0)rt=i;}for(int i=1;i<=m;i++)//并查集縮點{int u,v;scanf("%d%d",&u,&v);nt[u]=v;ban[v]=true;//v被縮到u的集合中去，在新圖中相當于被ban掉了merge(u,v);}for(int i=1;i<=n;i++)//縮點{if(ban[i])continue;id++;int pos=i;while(pos&&!c[pos])//注意這里會出現環的情況{ord[pos]=dcc[id].size();dcc[id].push_back(pos);c[pos]=id;pos=nt[pos];}}for(int i=1;i<=n;i++)//如果拓撲存在環的話，就不會被遍歷到if(!c[i])return 0*puts("0");for(int i=1;i<=n;i++)//建邊{if(i==rt)continue;if(c[i]!=c[p[i]]){node[c[p[i]]].push_back(c[i]);du[c[i]]++;}else if(ord[p[i]]>ord[i])//特判return 0*puts("0");}if(topo(c[rt])!=id)//拓撲中有環return 0*puts("0");for(auto it:ans)printf("%d ",it);puts("");return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1463E Plan of Lectures(拓扑排序+并查集缩点)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。