Skip to content

Instantly share code, notes, and snippets.

@balamark
Created April 5, 2015 19:00
Show Gist options
  • Save balamark/69580f03def18584d201 to your computer and use it in GitHub Desktop.
Save balamark/69580f03def18584d201 to your computer and use it in GitHub Desktop.
set lambda compare with pair<int, int>
/* Note we compare both first and second element. If we only compare the first, inserting with equal key will fail.
* e.g. {4,5} {4,6} will only insert {4,5} although {4,6} is also a valid pair we want here.
*/
auto comp = [](const ii &l, const ii &r) {return l.first==r.first?l.second<r.second:l.first<r.first;};
/*
* Use decltype to inspects the declared type of an entity or queries the return type of an expression.
*/
set<ii, decltype(comp)> bridges(comp);
int counter=0, critical_links=0;
void ArticulationPoint(int u){
dfs_num[u]=dfs_low[u]=counter++;
for(int j=0;j<(int)adj_list[u].size();++j){
int v = adj_list[u][j];
if(dfs_num[v]==kUnvisited){
dfs_parent[v] = u;
if(u==dfs_root) root_children++;
ArticulationPoint(v);
if(dfs_low[v]>dfs_num[u]){
critical_links++;
ii p = u < v ? make_pair(u,v) : make_pair(v,u);
auto q = bridges.insert(p);
}
dfs_low[u] = min(dfs_low[u], dfs_low[v]);
}
else if(v != dfs_parent[u]){
dfs_low[u] = min(dfs_low[u], dfs_num[v]);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment