社区讨论
站外题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 条回复,欢迎继续交流。
正在加载回复...