社区讨论

站外题RE求调

题目总版参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mifs38ta
此快照首次捕获于
2025/11/26 17:04
3 个月前
此快照最后确认于
2025/11/26 18:22
3 个月前
查看原帖
题面大意:输入一个有n个点m条边的有向图,删除图里的所有环并使图中每个点的入度减出度不变。
最后把剩下的图输出
CPP
//题面中的样例
输入
3 4
1 2
2 3
3 1
1 3
输出
1
1 3
//RE的样例
输入
3 6
1 2
1 3
2 1
2 3
3 1
3 2
我的代码输出:
FUCK1FUCK2
1 2 FUCK1FUCK2
2 1 Del 2 1
del 1 2
del ended
1 3 FUCK1FUCK2
3 1 Del 3 1
del 1 3
del ended

CPP
//这是我的代码,里面有调试
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000010,MAXM=1000010;
int n,m,u,v,a[MAXN],l;
bool vis[MAXN],completed[MAXN];
int abnormal_exit=0;
set<int>G[MAXN];
bool dfs(int u){
    cerr<<"FUCK1";
    if(completed[u])return 0;
    cerr<<"FUCK2\n";
    vis[u]=1;
    a[l]=u;
    l++;
    for(int v:G[u]){
        cerr<<u<<' '<<v<<' ';
        if(vis[v]){
            abnormal_exit=v;
            vis[u]=0;
            l--;
            G[u].erase(v);
            cerr<<"Del "<<u<<' '<<v<<'\n';
            return 1;
        }else{
            if(dfs(v)){
                G[u].erase(v);
                cerr<<"del "<<u<<' '<<v<<'\n';
                if(abnormal_exit!=u){
                    vis[u]=0;
                    l--;
                    return 1;
                }
                cerr<<"del ended\n";
            }
        }
    }
    vis[u]=0;
    l--;
    completed[u]=1;
    return 0;
}
int ans1[MAXM],ans2[MAXM],tot=0;
int main(){
    freopen("dag.in","r",stdin);
    freopen("dag.out","w",stdout);
    cin>>n>>m;
    while(m--){
        cin>>u>>v;
        G[u].insert(v);
    }
    for(int i=1;i<=n;i++){
        dfs(i);
    }
    for(int i=1;i<=n;i++){
        for(int u:G[i]){
            ans1[tot]=i,ans2[tot]=u,tot++;
        }
    }
    cout<<tot<<'\n';
    for(int i=0;i<tot;i++){
        cout<<ans1[i]<<' '<<ans2[i]<<'\n';
    }
    return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...