SPF

From Progteam

Revision as of 23:44, 15 July 2008 by Jinho (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by jinho.


SPF
Problem Number 1523
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;
}
Personal tools