QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#587730#3846. Link-Cut TreeSocialPandaRE 0ms3632kbC++236.3kb2024-09-24 21:16:472024-09-24 21:16:48

Judging History

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

  • [2024-09-24 21:16:48]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3632kb
  • [2024-09-24 21:16:47]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define double long double
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define endl "\n"
#define PII pair<int,int>
#define Gheap priority_queue<int,vector<int>,greater<int>>
#define Lheap priority_queue<int>
#define MAXN 0x3f3f3f3f
#define MINN -0x3f3f3f3f
using namespace std;

struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n + 1); // Adjusted to n+1 for 1-based indexing
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }
    
    int find_set(int x) {
        if (f[x] != x)
            f[x] = find_set(f[x]);
        return f[x];
    }
    
    bool same_set(int x, int y) {
        return find_set(x) == find_set(y);
    }
    
    bool merge_set(int x, int y) {
        int fx = find_set(x);
        int fy = find_set(y);
        if (fx == fy) {
            return false;
        }
        if (siz[fx] < siz[fy]) {
            swap(fx, fy);
        }
        f[fy] = fx;
        siz[fx] += siz[fy];
        return true;
    }
};

vector<int> cycle_edges;
unordered_map<int, vector<PII>> edge;
int cycle_start = -1, cycle_end = -1;
bool found_cycle = false;

void dfs(int u, int parent, int parent_eid) {
    for(auto &[v, eid] : edge[u]) {
        if(v == parent && eid == parent_eid) continue; // Skip the edge leading back to parent
        if(found_cycle) return; // If cycle is already found, no need to continue
        if(cycle_start == -1 && cycle_end == -1 && found_cycle == false && false) {
            // Placeholder if additional conditions are needed
        }
        if(cycle_start != -1 && cycle_end != -1 && u == cycle_start) {
            found_cycle = true;
            return;
        }
        if(edge.find(v) != edge.end()) {
            // To prevent processing non-existent nodes
        }
        // If the node is already visited and it's not the parent, a cycle is detected
        if(cycle_start == -1 && cycle_end == -1 && false) {
            // Placeholder for any specific conditions
        }
        // Use a visited map or global visited array if necessary
    }
}

vector<int> path;
bool visited_dfs = false;

void find_cycle(int u, int parent, int parent_eid) {
    // Mark the current node as visited
    // Assuming st is a global visited map
    // st[u] = 1; // Uncomment if using a visited map
    for(auto &[v, eid] : edge[u]) {
        if(v == parent) continue;
        if(cycle_start != -1 && cycle_end != -1 && v == cycle_start) {
            // Cycle completed
            cycle_edges.pb(eid);
            found_cycle = true;
            return;
        }
        if(find(cycle_edges.begin(), cycle_edges.end(), eid) != cycle_edges.end()) {
            continue; // Skip if already part of the cycle
        }
        if(/* Check if 'v' is visited */ false) { // Implement your visited logic
            if(!found_cycle) {
                cycle_start = v;
                cycle_end = u;
                cycle_edges.pb(eid);
            }
        } else {
            cycle_edges.pb(eid);
            find_cycle(v, u, eid);
            if(found_cycle) return;
            // If cycle not found in this path, remove the edge
            cycle_edges.pop_back();
        }
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;
    DSU dsu(n*10);
    edge.clear();
    cycle_edges.clear();
    cycle_start = -1;
    cycle_end = -1;
    found_cycle = false;

    int point = -1;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        if(dsu.same_set(a, b))
        {
            edge[a].pb({b, i});
            edge[b].pb({a, i});
            point = a;
            break;
        }
        edge[a].pb({b, i});
        edge[b].pb({a, i});
        dsu.merge_set(a, b);
    }

    // Read remaining edges if any
    for(int i = point != -1 ? m - (m - 1) : 0; i < m; i++) {
        // Handle remaining edges if needed
    }

    if(point == -1) {
        cout << "-1\n";
    }
    else {
        // Initialize visited map
        unordered_map<int, bool> st;
        // Start DFS to find the cycle edges
        // Modify the find_cycle function to use 'st' for visited nodes
        // Here's an improved DFS implementation that records the cycle edges

        cycle_edges.clear();
        stack<pair<int, int>> s; // Pair of (node, edge_id)
        // Use a parent map to reconstruct the cycle
        unordered_map<int, pair<int, int>> parent_map;

        function<void(int, int)> dfs_cycle = [&](int u, int parent_eid) {
            st[u] = true;
            for(auto &[v, eid] : edge[u]) {
                if(eid == parent_eid) continue;
                if(st[v] && v != parent_map[u].first) {
                    // Cycle detected, reconstruct the cycle
                    cycle_start = v;
                    cycle_end = u;
                    cycle_edges.pb(eid);
                    int current = u;
                    while(current != v) {
                        int p = parent_map[current].first;
                        int pe = parent_map[current].second;
                        cycle_edges.pb(pe);
                        current = p;
                    }
                    found_cycle = true;
                    return;
                }
                if(!st[v]) {
                    parent_map[v] = {u, eid};
                    dfs_cycle(v, eid);
                    if(found_cycle) return;
                }
            }
        };

        dfs_cycle(point, -1);

        if(cycle_edges.empty()) {
            cout << "-1\n";
        }
        else {
            // Remove duplicates and reverse to correct order if necessary
            // Sort the edge indices as per the user's original intention
            sort(cycle_edges.begin(), cycle_edges.end());
            // Print the edge indices
            for(int i = 0; i < cycle_edges.size(); i++) {
                cout << cycle_edges[i];
                if(i != cycle_edges.size() - 1) cout << ' ';
            }
            cout << '\n';
        }
    }
}

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt=1;
    cin >> tt;
    while(tt--) solve();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3632kb

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: -100
Runtime Error

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:


result: