QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203869#3846. Link-Cut Treeushg8877WA 1ms6804kbC++201.1kb2023-10-06 21:21:462023-10-06 21:21:46

Judging History

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

  • [2023-10-06 21:21:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6804kb
  • [2023-10-06 21:21:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e5+5;
int n,m;
int eu[MAXN],ev[MAXN],fa[MAXN];
vector<int> edg[MAXN];int deg[MAXN];
bool used[MAXN];
int find(int x){
	while(x^fa[x]) x=fa[x]=fa[fa[x]];
	return x;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i,edg[i].clear();
	for(int i=1;i<=m;i++) cin>>eu[i]>>ev[i],used[i]=false;
	for(int i=1;i<=m;i++) {
		edg[eu[i]].push_back(i);
		edg[ev[i]].push_back(i);used[i]=true;
		if(find(eu[i])!=find(ev[i])) fa[find(eu[i])]=find(ev[i]);
		else{
			for(int j=1;j<=n;j++) deg[j]=edg[j].size();
			queue<int> q;
			for(int j=1;j<=n;j++) if(deg[j]==1) q.push(j);
			while(!q.empty()){
				int u=q.front();q.pop();
				for(int i:edg[u]){
					int v=(eu[i]==u?ev[i]:eu[i]);
					used[i]=false;
					if(--deg[v]==1){
						q.push(v);
					} 
				}
			}
			for(int j=1;j<=m;j++) if(used[j]) cout<<j<<" \n"[j==i];
			cout<<endl;
			return;
		}
	}
	cout<<"-1"<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	int _;cin>>_;
	while(_--) solve(); 
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 6804kb

input:

2
6 8
1 2
2 3
5 6
3 4
2 5
5 4
5 1
4 2
4 2
1 2
4 3

output:

2 4 5 6

-1

result:

wrong answer 2nd lines differ - expected: '-1', found: ''