Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
articulation points (http://codeforces.com/contest/732/problem/F)
#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define mp make_pair #define pb push_back const int N = 4e5 + 5; vector<int> g[N]; int low[N], dis[N], timer = 0, vis[N] = {0}; int disjoint[N] = {0}, labels[N]; vector<int> bridgeTree[N]; vector<pii> bridgeNode[N]; map<pii, int> bridg; map<pii, int> id; vector<pii> edge; void dfs(int s, int p){ low[s] = dis[s] = timer++; vis[s] = 1; for(auto i : g[s]){ if(!vis[i]){ dfs(i, s); low[s] = min(low[s], low[i]); if(dis[s] < low[i]){ //it is a bridge as no node in the subtree of 'i' has a link to the upper nodes. bridg[mp(min(i, s), max(i,s))] = 1; } } else if(i != p){ //it is visited, so, it means that it is a upper node and for upper node we know that //it is yet to be explored (as it is dfs in undirected graph) low[s] = min(low[s], dis[i]); } } } void connectedComponents(int s, int lbl){ labels[s] = lbl; disjoint[lbl]++; vis[s] = 1; for(auto i : g[s]) if(!vis[i]){ if(bridg[mp(min(i,s), max(i,s))]) continue; connectedComponents(i, lbl); } } void joinComponent(int s, int p, int lbl){ vis[s] = 1; for(auto i : g[s]){ if(vis[i] == 2 || i == p || bridg[mp(min(i, s), max(i, s))]) continue; int idx = id[mp(min(i, s), max(i, s))]; edge[idx] = mp(s, i); if(vis[i] == 0) joinComponent(i, s, lbl); } vis[s] = 2; } void buildTree(int s){ vis[s] = 1; for(auto i : g[s]){ if(vis[i]) continue; if(bridg[mp(min(i, s), max(i, s))]){ bridgeTree[labels[s]].pb(labels[i]), bridgeNode[labels[s]].pb(mp(s, i)); bridgeTree[labels[i]].pb(labels[s]), bridgeNode[labels[i]].pb(mp(i, s)); } buildTree(i); } } void bridgeDfs(int s, int p){ for(int i = 0; i < (int)bridgeTree[s].size(); i++){ int lbl = bridgeTree[s][i], u = bridgeNode[s][i].first, v = bridgeNode[s][i].second; if(lbl == p) continue; int idx = id[mp(min(u, v), max(u, v))]; edge[idx] = mp(v, u); bridgeDfs(lbl, s); } } int solve(int n){ memset(vis, 0, sizeof(vis)); for(int j = 1; j <= n; j++) if(!vis[j]) dfs(j, 0); int lbl = 1; memset(vis, 0, sizeof(vis)); for(int j = 1; j <= n; j++) if(!vis[j]) connectedComponents(j, lbl++); memset(vis, 0, sizeof(vis)); for(int j = 1; j <= n; j++) if(!vis[j]) joinComponent(j, 0, labels[j]); int mx = 0, src = -1; for(int j = 1; j < lbl; j++) if(disjoint[j] > mx) mx = disjoint[j], src = j; memset(vis, 0, sizeof(vis)); buildTree(1); bridgeDfs(src, 0); return mx; } int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for(int j = 0; j < m; j++){ int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); id[mp(min(u, v), max(u, v))] = j; edge.pb(mp(u, v)); } cout << solve(n) << endl; for(auto i : edge) cout << i.first << " " << i.second << endl; return 0; }
run
|
edit
|
history
|
help
0
CirclQ
Overland pg. 68
My billing system
code
test yield
Listas enlazadas - dividir lista en dos reutilizando nodos
Display all prime numbers upto N without sieve
CPP Multi Inherit
IAR compiler bug test code
Two-phase sample with GCC