QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203869 | #3846. Link-Cut Tree | ushg8877 | WA | 1ms | 6804kb | C++20 | 1.1kb | 2023-10-06 21:21:46 | 2023-10-06 21:21:46 |
Judging History
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: ''