題目鏈接：點擊查看
題目大意：給出 n 個變量以及 m 個不等式，要求給 n 個變量分配作用域，使得所有不等式成立的前提下，“所有”的出現次數最多，給出一種構造方案
題目分析：因為有 m 個不等式的限制，結合樣例畫了畫圖，感覺像是拓撲排序，比賽時大膽猜測了一個結論：建好圖后如果圖中有環，答案為 -1 ，否則入度為 0 的點全部都為 A 就行了，第二天起床后果然沒過，經過和隊友的討論后，發現漏掉了兩個點：
不能只考慮正向拓撲，也得考慮反向拓撲，比如 3 2 3 1 3 2 這組數據不能用 bfs 實現拓撲，要用 dfs 實現拓撲，因為 bfs 只能從入度為 0 的點開始拓撲，而我們需要按照變量的出現順序進行拓撲，自然而然需要用 dfs 了，比如 3 2 1 2 1 3 這組數據
然后實現就行了，正向反向各寫一個dfs用來拓撲
代碼：
?
#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>
using namespace std;typedef long long LL;typedef unsigned long long ull;const LL inf=0x3f3f3f3f;const int N=2e5+100;vector<int>node1[N],node2[N];//正向邊和反向邊int c1[N],c2[N]; bool dfs1(int u)//正向拓撲
{c1[u]=-1;for(auto v:node1[u]){if(c1[v]<0)return false;else if(!c1[v]&&!dfs1(v))return false;}c1[u]=1;return true;
}bool dfs2(int u)//反向拓撲
{c2[u]=-1;for(auto v:node2[u]){if(c2[v]<0)return false;else if(!c2[v]&&!dfs2(v))return false;}c2[u]=1;return true;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);while(m--){int u,v;scanf("%d%d",&u,&v);node1[u].push_back(v);node2[v].push_back(u);}int ans=0;string res;for(int i=1;i<=n;i++){if(!c1[i]&&!c2[i])//如果當前點還沒有遍歷過，也就是沒有限制，則用A{ans++;res+="A";}else//有限制就用Eres+="E";if(!dfs1(i)||!dfs2(i))//拓撲找環return 0*puts("-1");}cout<<ans<<endl<<res<<endl;return 0;
}
?
總結
以上是生活随笔為你收集整理的CodeForces - 1345E Quantifier Question(dfs实现拓扑序)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
