QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#790422#3846. Link-Cut TreeYurily#AC ✓853ms26812kbC++202.5kb2024-11-28 11:46:292024-11-28 11:46:30

Judging History

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

  • [2024-11-28 11:46:30]
  • 评测
  • 测评结果:AC
  • 用时:853ms
  • 内存:26812kb
  • [2024-11-28 11:46:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+5;
vector<int> g[MAX];
struct edge{
    int from,to;
};
edge e[MAX];
int n,m,fa[MAX];
stack<int> st;
bool flag,vis[MAX];
map<pair<int,int>,int> edg;
int ans[MAX],cnt,anse[MAX];
void dfs(int u,int fr){
    if(flag)
        return;
    st.push(u);
    for(auto i=g[u].begin();i!=g[u].end();++i){
        int v=(*i);
        if(v==fr||v==u)
            continue;
        if(flag)
            return;
        if(vis[v]){
            flag=1;
            while(st.top()!=v){
                ans[++cnt]=st.top();
                st.pop();
            }
            ans[++cnt]=v;
            return;
        }
        else{
            vis[v]=1;
            dfs(v,u);
        }
    }
    if(flag)
        return;
    st.pop();
}
int findf(int x){
    if(fa[x]==x)
        return x;
    fa[x]=findf(fa[x]);
    return fa[x];
}
void solve(){
    edg.clear();
    while(!st.empty())
        st.pop();
    cnt=0;
    flag=0;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        fa[i]=i;
    }
    memset(vis,0,sizeof(bool)*(n+1));
    for(int i=1;i<=n;++i)
        g[i].clear();

    for(int i=1;i<=m;++i){
        cin>>e[i].from>>e[i].to;
        if(!edg[make_pair(e[i].from,e[i].to)]){
            edg[make_pair(e[i].from,e[i].to)]=i;
            edg[make_pair(e[i].to,e[i].from)]=i;
        }
    }

    int tot=0;
    for(int i=1;i<=m;++i){
        tot=i;
        int r1=findf(e[i].from),r2=findf(e[i].to);
        if(r1!=r2){
            fa[r2]=r1;
        }
        else{
            break;
        }
    }

    for(int i=1;i<=tot;++i){
        g[e[i].from].push_back(e[i].to);
        g[e[i].to].push_back(e[i].from);
    }

    for(int i=1;i<=n;++i){
        if(!vis[i]&&!flag){
            vis[i]=1;
            dfs(i,0);
        }
    }
    if(flag){
        anse[1]=edg[make_pair(ans[1],ans[2])];
        for(int i=2;i<=cnt-1;++i){
            anse[i]=edg[make_pair(ans[i],ans[i+1])];
        }
        anse[cnt]=edg[make_pair(ans[cnt],ans[1])];

        sort(anse+1,anse+1+cnt);
        cout<<anse[1];
        for(int i=2;i<=cnt;++i)
            cout<<" "<<anse[i];
        cout<<"\n";
    }
    else{
        cout<<"-1\n";
    }
}
int main(){
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int T;
    cin>>T;
    while(T--){
        solve();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3636kb

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:

ok 2 lines

Test #2:

score: 0
Accepted
time: 853ms
memory: 23628kb

input:

1658
9 20
6 4
5 8
1 7
2 3
3 8
3 1
4 8
5 3
7 6
1 6
4 9
4 1
9 3
2 5
4 5
8 9
1 8
4 2
5 7
3 6
14 78
13 12
10 8
2 10
6 13
2 14
13 1
14 10
9 6
2 13
8 3
9 8
5 6
14 12
8 1
9 14
9 5
12 6
5 10
3 12
10 4
8 5
9 10
6 8
1 6
12 4
3 13
1 5
10 3
13 9
10 13
2 5
4 7
7 1
7 6
9 3
2 12
1 10
9 1
1 14
3 1
3 4
11 1
11 6
7 1...

output:

2 5 8
3 5 7
1 3 4
2 3 4
2 3 4 7 13
1 3 4 5 9
3 4 7 12
1 2 3
8 10 11
2 3 5 7 12 13 14 15 16
1 2 3 5
1 2 4
1 3 4
1 2 3
1 2 3
10 11 15
1 5 6
1 5 7
1 2 3 4
-1
1 3 6
-1
1 2 3 5
-1
-1
6 8 9 10 11 16
1 2 6
2 3 4
-1
-1
7 8 12 13 18
-1
1 4 8 12
3 5 10
4 6 8
1 2 3 4
3 5 6
5 8 10 15
4 6 8
-1
1 2 3 5 6
1 3 4
1 ...

result:

ok 1658 lines

Test #3:

score: 0
Accepted
time: 516ms
memory: 26812kb

input:

10
100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 10 lines