QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363423 | #2341. Dead-End Detector | TWTP_TCTF# | WA | 195ms | 132056kb | C++14 | 3.4kb | 2024-03-23 22:15:56 | 2024-03-23 22:15:57 |
Judging History
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(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: 10ms
memory: 60760kb
Test #2:
score: 0
Accepted
time: 7ms
memory: 61704kb
Test #3:
score: 0
Accepted
time: 195ms
memory: 132056kb
Test #4:
score: 0
Accepted
time: 5ms
memory: 59716kb
Test #5:
score: 0
Accepted
time: 11ms
memory: 59060kb
Test #6:
score: 0
Accepted
time: 7ms
memory: 60652kb
Test #7:
score: -100
Wrong Answer
time: 3ms
memory: 61752kb