QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363422#2341. Dead-End DetectorTWTP_TCTF#RE 6ms37944kbC++143.4kb2024-03-23 22:15:212024-03-23 22:15:21

Judging History

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

  • [2024-03-23 22:15:21]
  • 评测
  • 测评结果:RE
  • 用时:6ms
  • 内存:37944kb
  • [2024-03-23 22:15:21]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7;

vector<int> adj[N], bridge_tree[N], nodes_of_color[N], bridges_tal3a[N];
int dfsn[N], low[N], cost[N], timer, cnt, comp_id[N], comp_sz[N], subtree_total[N], kam[N], color[N], in[N];
stack<int> st;
map<pair<int, int>, bool> mark;
vector<pair<int, int>> ans;

void dfs(int node, int par, int c){
    nodes_of_color[c].push_back(node);
    color[node] = c;
    dfsn[node] = low[node] = ++timer;
    st.push(node);
    for(auto i: adj[node]){
        if(i == par) continue;
        if(dfsn[i] == 0){
            dfs(i, node, c);
            low[node] = min(low[node], low[i]);
        }
        else low[node] = min(low[node], dfsn[i]);
    }
    if(dfsn[node] == low[node]){
        cnt++;
        while(1){
            int cur = st.top();
            st.pop();
            comp_id[cur] = cnt;
            comp_sz[cnt]++;
            if(cur == node) break;
        }
    }
}

void dfs2(int x, int par){
    subtree_total[x] = comp_sz[x] > 1;
    for(auto &y: bridge_tree[x]){
        if(y == par)
            continue;
        mark[{x, y}] = true;
        dfs2(y, x);
        subtree_total[x] += subtree_total[y];
    }
}

void solve(int c){
    for(auto &i: nodes_of_color[c]){
        for(auto j: adj[i]){
            if(comp_id[i] != comp_id[j]){
                bridge_tree[comp_id[i]].push_back(comp_id[j]);
            }
        }
    }
    int root = comp_id[nodes_of_color[c][0]];
    dfs2(root, -1);
    int total = subtree_total[root];
    for(auto &i: nodes_of_color[c]){
        for(auto j: adj[i]){
            if(i > j)
                continue;
            if(comp_id[i] != comp_id[j]){
                if(mark[{comp_id[i], comp_id[j]}]){
                    if(subtree_total[comp_id[j]] == 0){
                        // critical
                        bridges_tal3a[i].push_back(j);
                        in[j]++;
                    }
                }else{
                    if(total - subtree_total[comp_id[j]] == 0){
                        // critical
                        bridges_tal3a[j].push_back(i);
                        in[i]++;
                    }
                }
            }
        }
    }
    for(auto &i: nodes_of_color[c]){
        if(in[i] == 0){
            for(auto &j: bridges_tal3a[i])
                ans.push_back({i, j});
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n, m;
    cin >> n >> m;
    while(m--){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for(int node = 1, c = 1; node <= n; node++){
        if(color[node] == 0){
            dfs(node, 0, c);
            bool is_tree = true;
            for(auto &cur_node: nodes_of_color[c]){
                is_tree &= comp_sz[comp_id[cur_node]] == 1;
            }
            if(is_tree){
                for(auto &cur_node: nodes_of_color[c]){
                    if(adj[cur_node].size() == 1)
                        ans.push_back({cur_node, adj[cur_node][0]});
                }
            }else{
                solve(c);
            }
            c++;
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(auto &p: ans)
        cout << p.first << ' ' << p.second << '\n';
    return 0;
}

Details

Test #1:

score: 100
Accepted
time: 4ms
memory: 37452kb

Test #2:

score: 0
Accepted
time: 6ms
memory: 37944kb

Test #3:

score: -100
Runtime Error