QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#818933#9875. Don't Detect CycleNKheyuxiangWA 0ms3860kbC++14929b2024-12-18 10:56:362024-12-18 10:56:36

Judging History

你现在查看的是最新测评结果

  • [2024-12-18 10:56:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3860kb
  • [2024-12-18 10:56:36]
  • 提交

answer

#include<bits/stdc++.h>
#define N 4005
using namespace std;
int n,m,tot;
int U[N],V[N],R[N],P[N];
bool vis[N];
void del(int i){
	vis[i]=1;
	P[++tot]=i;
	R[U[i]]--,R[V[i]]--;
}
void solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) R[i]=0;
	for(int i=1;i<=m;i++){
		vis[i]=0;
		scanf("%d%d",&U[i],&V[i]);
		R[U[i]]++;
		R[V[i]]++;
	}
	tot=0;
	while(1){
		int u=0,v=0;
		for(int i=1;i<=n;i++)
			if(R[i]==1) u=i;
		if(u){
			for(int i=1;i<=m;i++)
				if(!vis[i]&&(U[i]==u||V[i]==u)) del(i);
			continue;
		}
		for(int i=1;i<=m;i++){
			if(vis[i]) continue;
			if(R[U[i]]==2&&R[V[i]]==2){del(i),u=U[i],v=V[i];break;}
		}
		if(!u) break;
		for(int i=1;i<=m;i++)
			if(!vis[i]&&(U[i]==u||U[i]==v||V[i]==u||V[i]==v)) del(i);
	}
	if(tot!=m) puts("-1");
	else{
		for(int i=m;i>=1;i--) printf("%d ",P[i]);
		printf("\n");
	}
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--) solve();
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3860kb

input:

1
4 4
1 2
2 3
3 4
4 2

output:

4 3 2 1 

result:

wrong answer Wrong - you detected cycles