CodeForces – 1345E Quantifier Question(dfs实现拓扑序)Falcon的博客-

题目链接：点击查看

题目大意：给出 n 个变量以及 m 个不等式，要求给 n 个变量分配作用域，使得所有不等式成立的前提下，“所有”的出现次数最多，给出一种构造方案

题目分析：因为有 m 个不等式的限制，结合样例画了画图，感觉像是拓扑排序，比赛时大胆猜测了一个结论：建好图后如果图中有环，答案为 -1 ，否则入度为 0 的点全部都为 A 就行了，第二天起床后果然没过，经过和队友的讨论后，发现漏掉了两个点：

1. 不能只考虑正向拓扑，也得考虑反向拓扑，比如 3 2 3 1 3 2 这组数据
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//有限制就用E    res+="E";   if(!dfs1(i)||!dfs2(i))//拓扑找环    return 0*puts("-1");  }  cout<<ans<<endl<<res<<endl;                 return 0; }