# SPF

### From Progteam

Sorter: | Mlc413 |
---|---|

Source: | Unknown |

Link: | http://acm.pku.edu.cn/JudgeOnline/problem?id=1523 |

**SPF** is problem number 1523 on the Peking University ACM
site.

Paul's solution:

#include <map> #include <set> #include <iostream> using namespace std; typedef set<int> VERTEX_LIST; typedef map<int, set<int> > UGRAPH; map<int, bool> visited; map<int, int> parent; map<int, int> num; map<int, int> low; map<int, int> AP; const int ROOT = 1; const int HOLDER = 1; //The number of unique "low" numbers in the neighbors of the articulation point // signifies the number of subnets that would be created by the removal of the // articulation point. This function is only useful AFTER the all the vertices // in the graph have been processed by findAP(). int subnetCheck(UGRAPH &graph, int v) { set<int> check; set<int>::iterator sitr; set<int> &neighbors = graph[v]; for(sitr = neighbors.begin(); sitr != neighbors.end(); ++sitr) { int w = *sitr; check.insert(low[w]); } return check.size(); } //Main function that looks for articulation points void findAP(UGRAPH &graph, int v, int counter) { visited[v] = true; low[v] = counter; num[v] = counter; //For each neighbor w of v do: set<int>::iterator sitr; set<int> &neighbors = graph[v]; for(sitr = neighbors.begin(); sitr != neighbors.end(); ++sitr) { int w = *sitr; //If w not yet visited do: if (!visited[w]) { //w.parent = v parent[w] = v; //DFS findAP(graph, w, ++counter); //Update v.low low[v] = min(low[v], low[w]); //if v is not the root and the w.low > v.num do: if ((num[v] != ROOT) && (low[w] >= num[v])) { //We have found an articulation point //However we cannot tell how many subnets remain till after // all vertices in the graph have been processed by findAP() //So just set up a temporary HOLDER variable. AP[v] = HOLDER; } //Else w has already been visited, do: } else { //if v.parent != w: // we have a back-edge! if (parent[v] != w) { //update v.low to be the min(v.low, w.num) low[v] = min(low[v], num[w]); } } } //If we are done finally finished the DFS and have returned back to // the root of the new DFS tree then: if (ROOT == num[v]) { //Check how many subnets might exist if we remove the root. //Most online sources say that its sufficient to check whether // the root has 2 or more children, in which case the root is // definitely an articulation point. However this is only true // if the children of the root are not connected to each other. // So if the children have different "low" numbers, then we're // okay since that means they're not interconnected to each other. int root_check = subnetCheck(graph, v); if (2 <= root_check) { AP[v] = root_check; } //Going to perform subnetCheck() on each of the nodes we identified // as being articulation points to properly find out how many // subnets are left over once we remove those vertices. map<int, int>::iterator mitr; for (mitr = AP.begin(); mitr != AP.end(); ++mitr) { int ap_node = mitr->first; int val = mitr->second; if (val == HOLDER) { AP[ap_node] = subnetCheck(graph, ap_node); } } } } //Driver for the findAP() function void findAPDriver(UGRAPH &graph, int root) { //Run the DFS on the arbitrarily chosen root vertex. findAP(graph, root, ROOT); //Annoying printing requirements for PKU map<int, int>::iterator itr; if (0 < AP.size()) { for (itr = AP.begin(); itr != AP.end(); ++itr) { cout << " SPF node " << itr->first << " leaves " << itr->second << " subnets" << endl; } } else { cout << " No SPF nodes" << endl; } } int main() { UGRAPH graph; VERTEX_LIST vlist; int network = 1; int root = -1; while (true) { int a, b; cin >> a; cin >> b; if (0 == a) { //Annoying printing requirements for PKU if (network > 1) cout << endl; cout << "Network #" << network++ << endl; findAPDriver(graph, root); graph.clear(); vlist.clear(); visited.clear(); parent.clear(); num.clear(); low.clear(); AP.clear(); root = -1; if (0 == b) { break; } else { a = b; cin >> b; } } //Arbitrarily choosing a root vertex if (-1 == root) root = a; //Initializing the vertex "fields" visited[a] = visited[b] = false; parent[a] = parent[b] = -1; num[a] = num[b] = -1; low[a] = low[b] = -1; //Adding the vertices to the undirected graph graph[a].insert(b); graph[b].insert(a); } return 0; }