题解 CF915D 【Almost Acyclic Graph】

这道题我第一次的想法是直接判环的数量，然而事实证明实在是太naive了。

随便画个图都可以卡掉我的解法。（不知道在想什么）

这道题的正解是拓扑排序。

朴素的想法是对所有边都跑一次拓扑，但这样$O(m(n+m))$会炸，于是可以有下面的优化。

我们找到所有入度不为零的点，然后把他们每一个都删掉一条边跑一遍拓扑排序。

那么这样就可以优化到$O(n(n+m))$了，稳得一批。

AC代码如下：

1935ms 1356kb

 #include<bits/stdc++.h>

 using namespace std;

 namespace StandardIO {

     template<typename T>inline void read (T &x) {

         x=;T f=;char c=getchar();

         for (; c<''||c>''; c=getchar()) if (c=='-') f=-;

         for (; c>=''&&c<=''; c=getchar()) x=x*+c-'';

         x*=f;

     }

     template<typename T>inline void write (T x) {

         if (x<) putchar('-'),x*=-;

         if (x>=) write(x/);

         putchar(x%+'');

     }

 }

 using namespace StandardIO;

 namespace Solve {

     const int N=;

     int n,m;

     vector<int>graph[N];

     int indeg[N];

     queue<int>q;

     inline bool toposort (int n) {

         int temp[N],size=;

         memcpy(temp,indeg,sizeof(indeg));

         while (!q.empty()) q.pop();

         for (register int i=; i<=n; ++i) {

             if (temp[i]==) q.push(i),size++;

         }

         while (!q.empty()) {

             int v=q.front();q.pop();

             for (register int i=; i<graph[v].size(); ++i) {

                 int to=graph[v][i];

                 temp[to]--;

                 if (temp[to]==) q.push(to),size++;

             }

         }

         return size>=n;

     }

     inline void solve () {

         read(n),read(m);

         for (register int i=; i<=m; ++i) {

             int x,y;

             read(x),read(y);

             indeg[y]++;

             graph[x].push_back(y);

         }

         for (register int i=; i<=n; ++i) {

             if (indeg[i]!=) {

                 indeg[i]--;

                 if (toposort(n)) {

                     puts("YES");

                     return;

                 }

                 indeg[i]++;

             }

         }

         puts("NO");

     }

 }

 using namespace Solve;

 int main () {

 //    freopen(".in","r",stdin);

 //    freopen(".out","w",stdout);

     solve();

 }

巴特西

题解 CF915D 【Almost Acyclic Graph】

最新文章

热门文章