UVa 10178 – Count the Faces

for more explanation refer to this tut.

Using Euler’s Formula

#include <iostream>
#include <map>
#include <queue>
#include <algorithm>
#include <cstdio>
using namespace std;

#define BLACK 1
#define WHITE 0
#define RED -1
#define nNodes 58

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

bool v[nNodes];
//for the adjList used Pair<node, cost>
vector <vii> adjList;
int n;// # nodes in current graph

int solve(){
	//returns the number of faces using Euler Formula V − E + f = 2
	// using BFS on a adjList
	fill(v,v+n,WHITE);
	queue<int> q;
	int current, nEdge, nVertix, faces = 0;
	ii t;

	for (int i = 0 ; i < n; i++){
		if (v[i] == WHITE){
			q.push(i);
			nEdge = 0 ;
			nVertix = 0;
			while (!q.empty()){
				current = q.front() ;q.pop();
				if (v[current] == BLACK) continue ;
				for(int j = 0 ; j < (int)adjList[current].size() ;j++){
					t = adjList[current][j];
					if (v[t.first] == WHITE){
						q.push(t.first);
						nEdge++;
					}
				}
				v[current] = BLACK;
				nVertix++;

			}
		faces +=  2+nEdge-nVertix-1;
		}
	}
	return faces+1;
}

int main(){
	for (int i = 0 ; i < nNodes ; i++)
		adjList.push_back(vii());

	int e,next;
	char buffer[50];
	map<char, int> m;

	while (scanf ("%d %d",&n,&e) == 2){
		gets(buffer);
		next = 0;
		m.clear();
		for (int i = 0 ; i < n ; i++)
			adjList[i].clear();

		for (int i = 0 ; i < e ; i++){
			gets(buffer);
			if (m.find(buffer[0])==m.end())
				m[buffer[0]]=next++;
			if (m.find(buffer[2])==m.end())
				m[buffer[2]]=next++;

			adjList[m[buffer[0]]].push_back(ii(m[buffer[2]],1));
			if (buffer[0]!=buffer[2])
				adjList[m[buffer[2]]].push_back(ii(m[buffer[0]],1));
		}

		printf("%d\n",solve());
	}
}

Using Disjoint Sets

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std ;
#define nNodes 58

//disjoint Sets
int parent[nNodes];

void init(int n){
	n++;
	for (int i =0 ; i < n ; i ++)
		parent[i] = i;
}

int find(int i){
	return parent[i]==i?i:(parent[i] = find(parent[i]));
}

bool isSameSet(int i, int j){
	return find(i)==find(j);
}

void unionSets(int i, int j){
	parent[find(i)] = find(j);
}

//end of disjoint sets

int main(){
	int v,e,faces,next;
	char buffer[50];
	map<char, int> m;

	while (scanf ("%d %d",&v,&e) == 2){
		gets(buffer);
		init(v);
		faces = 0;
		m.clear();
		next = 0;

		for (int i = 0 ; i < e ; i++){
			gets(buffer);

			if (m.find(buffer[0])==m.end())
				m[buffer[0]]=next++;
			if (m.find(buffer[2])==m.end())
				m[buffer[2]]=next++;

			if(isSameSet(m[buffer[0]],m[buffer[2]]))
				faces++;
			unionSets(m[buffer[0]],m[buffer[2]]);
		}
		printf("%d\n",faces+1);// the added one is the outer face
	}
}
Advertisements

One thought on “UVa 10178 – Count the Faces

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s