QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#363445#2341. Dead-End DetectorTWTP_TCTF#AC ✓691ms223260kbC++143.5kb2024-03-23 22:38:242024-03-23 22:38:25

Judging History

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

  • [2024-03-23 22:38:25]
  • 评测
  • 测评结果:AC
  • 用时:691ms
  • 内存:223260kb
  • [2024-03-23 22:38:24]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 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(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]++;
                    }
                    if(total - subtree_total[comp_id[j]] == 0){
                        // critical
                        bridges_tal3a[j].push_back(i);
                        in[i]++;
                    }
                }else{
                   continue;
                }
            }
        }
    }
    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());
    if(ans.size() == 0){
        cout << 0;
    }else{
        cout << ans.size() << '\n';
        for(auto &p: ans)
            cout << p.first << ' ' << p.second << '\n';
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 60624kb

Test #2:

score: 0
Accepted
time: 7ms
memory: 62004kb

Test #3:

score: 0
Accepted
time: 199ms
memory: 130800kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 59684kb

Test #5:

score: 0
Accepted
time: 7ms
memory: 59840kb

Test #6:

score: 0
Accepted
time: 7ms
memory: 61300kb

Test #7:

score: 0
Accepted
time: 4ms
memory: 60632kb

Test #8:

score: 0
Accepted
time: 29ms
memory: 76076kb

Test #9:

score: 0
Accepted
time: 7ms
memory: 61264kb

Test #10:

score: 0
Accepted
time: 7ms
memory: 61112kb

Test #11:

score: 0
Accepted
time: 7ms
memory: 59012kb

Test #12:

score: 0
Accepted
time: 8ms
memory: 61176kb

Test #13:

score: 0
Accepted
time: 47ms
memory: 65400kb

Test #14:

score: 0
Accepted
time: 53ms
memory: 65880kb

Test #15:

score: 0
Accepted
time: 236ms
memory: 83776kb

Test #16:

score: 0
Accepted
time: 191ms
memory: 88160kb

Test #17:

score: 0
Accepted
time: 545ms
memory: 173000kb

Test #18:

score: 0
Accepted
time: 543ms
memory: 173224kb

Test #19:

score: 0
Accepted
time: 8ms
memory: 61828kb

Test #20:

score: 0
Accepted
time: 4ms
memory: 60972kb

Test #21:

score: 0
Accepted
time: 7ms
memory: 61876kb

Test #22:

score: 0
Accepted
time: 97ms
memory: 75596kb

Test #23:

score: 0
Accepted
time: 691ms
memory: 192924kb

Test #24:

score: 0
Accepted
time: 82ms
memory: 129212kb

Test #25:

score: 0
Accepted
time: 269ms
memory: 126116kb

Test #26:

score: 0
Accepted
time: 82ms
memory: 132092kb

Test #27:

score: 0
Accepted
time: 277ms
memory: 130656kb

Test #28:

score: 0
Accepted
time: 240ms
memory: 131732kb

Test #29:

score: 0
Accepted
time: 285ms
memory: 132216kb

Test #30:

score: 0
Accepted
time: 98ms
memory: 92900kb

Test #31:

score: 0
Accepted
time: 222ms
memory: 90560kb

Test #32:

score: 0
Accepted
time: 107ms
memory: 85848kb

Test #33:

score: 0
Accepted
time: 212ms
memory: 86748kb

Test #34:

score: 0
Accepted
time: 674ms
memory: 223260kb

Test #35:

score: 0
Accepted
time: 240ms
memory: 84076kb

Test #36:

score: 0
Accepted
time: 228ms
memory: 90460kb

Test #37:

score: 0
Accepted
time: 234ms
memory: 99892kb

Test #38:

score: 0
Accepted
time: 227ms
memory: 86164kb

Test #39:

score: 0
Accepted
time: 216ms
memory: 87108kb

Test #40:

score: 0
Accepted
time: 365ms
memory: 127040kb

Test #41:

score: 0
Accepted
time: 551ms
memory: 171372kb

Test #42:

score: 0
Accepted
time: 376ms
memory: 126692kb

Test #43:

score: 0
Accepted
time: 396ms
memory: 128032kb

Test #44:

score: 0
Accepted
time: 505ms
memory: 172376kb

Test #45:

score: 0
Accepted
time: 535ms
memory: 172668kb