POJ 1523問題解決報告

この問題は最初に見たのですが、カットポイントの計算方法が分かりませんでした.難しいと思いました.そして、私の大ニューヨークの問題を見て安心しました.暴力でやればいいです.やはり一回の提出で無事に済みました.ポイント番号が不連続かもしれないと思いますが、書くのはちょっと面倒くさいです.また、c+++中伝array引用の方法が分かりました.お目にかかるhttp://stackoverflow.com/questions/5724171/passing-an-array-by-reference

void Func(int (&myArray)[100])

Pass array of 100 int by reference the parameters name is myAray;
thestoryofs now
1523
Acceepted
188 K
0 MS
C++
2690 B

/* 
ID: thestor1 
LANG: C++ 
TASK: poj1523 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>

using namespace std;
const int MAXN = 1000;
class Edge
{
public:
	int v;
	Edge *next;
	Edge(): v(-1), next(NULL) {}
	Edge(int v): v(v), next(NULL) {}
};

int map2id(int ni, int mapping[], int rmapping[], int &node_id)
{
	// map from input (ni) to node_id
	// reverse mapping (rmapping) is also needed for output
	ni--;
	if (mapping[ni] < 0)
	{
		mapping[ni] = node_id;
		rmapping[node_id] = ni + 1;
		node_id++;	
	}
	return mapping[ni];
}

void addEdge(int ni, int nj, Edge* (&adjs)[MAXN])
{
	Edge* e = new Edge(nj);
	e->next = adjs[ni];
	adjs[ni] = e;
}

void addEdges(int ni, int nj, int mapping[], int rmapping[], int &node_id, Edge* (&adjs)[MAXN])
{
	ni = map2id(ni, mapping, rmapping, node_id);
	nj = map2id(nj, mapping, rmapping, node_id);

	addEdge(ni, nj, adjs);
	addEdge(nj, ni, adjs);
}

void dfs(int u, const int node, Edge* adjs[], bool (&visited)[MAXN])
{
	visited[u] = true;

	Edge *e = adjs[u];
	while (e != NULL)
	{
		int v = e->v;
		if (v != node && !visited[v])
		{
			dfs(v, node, adjs, visited);
		}
		e = e->next;
	}
}

int main()
{
	int network_id = 1;
	int mapping[MAXN], rmapping[MAXN];
	Edge* adjs[MAXN];
	bool visited[MAXN];
	while (true)
	{
		memset(mapping, -1, sizeof(int) * MAXN);
		for (int i = 0; i < MAXN; ++i)
		{
			adjs[i] = NULL;
		}

		int node_id = 0;
		int ni, nj;
		scanf("%d", &ni);
		if (ni == 0)
		{
			break;
		}
		scanf("%d", &nj);
		
		addEdges(ni, nj, mapping, rmapping, node_id, adjs);

		while (scanf("%d", &ni) && ni)
		{
			scanf("%d", &nj);
			addEdges(ni, nj, mapping, rmapping, node_id, adjs);
		}

		printf("Network #%d
", network_id);
		// printf("[debug]graph(%d):
", node_id);
		// for (int i = 0; i < node_id; ++i)
		// {
		// 	printf("%d: ", i);
		// 	Edge *e = adjs[i];
		// 	while (e != NULL)
		// 	{
		// 		printf("%d ", e->v);
		// 		e = e->next;
		// 	}
		// 	printf("
");
		// }

		bool nosubnet = true;
		for (int u = 0; u < node_id; ++u)
		{
			memset(visited, false, sizeof(bool) * node_id);
			int nsubnets = 0;
			for (int v = 0; v < node_id; ++v)
			{
				if (v == u || visited[v])
				{
					continue;
				}
				nsubnets++;
				dfs(v, u, adjs, visited);
			}

			if (nsubnets > 1)
			{
				nosubnet = false;
				printf("  SPF node %d leaves %d subnets
", rmapping[u], nsubnets);
			}
		}

		if (nosubnet)
		{
			printf("  No SPF nodes
");
		}

		printf("
");
		network_id++;
	}
		
	return 0;  
}