# SPF

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by jinho.

 Sorter: Mlc413 Unknown 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;
}
```