题解归档 - cf915D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf915D
• 本地来源：problems/cf915D/idea.md
• 题目链接：https://codeforces.com/contest/915/problem/D
• 原始标题：CF915D — Almost Acyclic Graph

思路

CF915D — Almost Acyclic Graph

题意

给定 n 点 m 边的有向图，问能否最多删一条边使其变为 DAG（无环）。

做法

1. Kahn 拓扑排序：若原图已是 DAG，输出 YES。
2. 否则枚举每条有向边 (u,v)，暂时删掉后再拓扑排序；若某次能排完 n 个点则 YES，否则 NO。

正确性：若删边 e 后无环，则 e 必至少属于一条环；枚举全部 m 条边不会漏解。n≤500, m≤10^5，每次拓扑 O(n+m)，总 O(m·(n+m)) 可过。

实现要点

• 跳过边用 (bu,bv) 传参，建入度与松弛时 if(x==bu and y==bv) continue。
• 无环检测用 topo(-1,-1)（顶点 1..n，不会误删）。
• topo 内循环变量勿与 main 外层枚举边的 i 共用，否则第一次调用后 i 被改成 n+1，外层循环提前结束（对拍曾 WA）。

曾踩坑

• 只枚举「DFS 找到的某条环」上的边：可能漏掉不在该环上、但删掉即可破环的边。
• 只枚举「环上顶点出发」的边：删 9→4 这类从 DAG 部分指向环的边会漏。
• DFS 沿 fa[] 回溯到 0 时会死循环，需限步或改 Kahn。

样例

• 样例 1：删 2→3 后无环 → YES。
• 样例 2：删任意一条边仍剩环 → NO。

验证

样例 + WSL 本地对拍 stress 500 组通过。

代码

来源：problems/cf915D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:34:24
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=505;
queue<ll>q;
vector<ll>ss[maxn+5];
ll indeg[maxn+5],n,m,i,j,k,u,v,zc,pd,cur,dq,cnt;
bool topo(ll bu,ll bv){
    ll x,y,z;
    for(x=1;x<=n;x++) indeg[x]=0;
    for(x=1;x<=n;x++){
        for(z=0;z<(ll)ss[x].size();z++){
            y=ss[x][z];
            if(x==bu and y==bv) continue;
            indeg[y]++;
        }
    }
    while(!q.empty()) q.pop();
    cnt=0;
    for(x=1;x<=n;x++) if(indeg[x]==0) q.push(x);
    while(!q.empty()){
        u=q.front();
        q.pop();
        cnt++;
        for(z=0;z<(ll)ss[u].size();z++){
            y=ss[u][z];
            if(u==bu and y==bv) continue;
            indeg[y]--;
            if(indeg[y]==0) q.push(y);
        }
    }
    return cnt==n;
}
int main(){
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>u>>v;
        ss[u].push_back(v);
    }
    if(topo(-1,-1)){
        cout<<"YES\n";
        return 0;
    }
    for(i=1;i<=n;i++){
        for(zc=0;zc<(ll)ss[i].size();zc++){
            dq=ss[i][zc];
            if(topo(i,dq)){
                cout<<"YES\n";
                return 0;
            }
        }
    }
    cout<<"NO\n";
    return 0;
}