OJ Board

Code: Select all

1
(A,B)
(B,C)
(B,D)
(D,E)
(F,G)
****
A,B,C,E

Code: Select all

#include <stdio.h>
#include <map>
#include <vector>

using namespace std;

typedef vector<int> vi;

class UnionFind{
	private: 
		vi p,rank;
		int singles, sets;
	public: 
		UnionFind(int N){
			singles=sets=N;
			rank.assign(N,0);
			p.assign(N,0);
			for(int i=0;i<N;i++)
				p[i]=i;
		}
		int findSet(int i){
			return (p[i]==i) ? i : (p[i]=findSet(p[i]));
		}
		bool isSameSet(int i,int j){
			return findSet(i)==findSet(j);
		}
		void unionSet(int i,int j){
			if(!isSameSet(i,j)){
				int x=findSet(i), y=findSet(j);
				sets--;
				if(rank[x]==0)
					singles--;
				if(rank[y]==0)
					singles--;
				if(rank[x]>rank[y]) 
					p[y]=x;
				else{
					p[x]=y;
					if(rank[x]==rank[y]) rank[y]++;
				}
			}
		}
		int getSingles(){
			return singles;
		}
		int getSets(){
			return sets;
		}
};

int main(){
	int TC, E, V, trees, acorns;
	char from[26],to[26],t;
	map<char,int> m;
	scanf("%d",&TC);
	while(TC--){
		E=0;
		m.clear();
		//scan in edges
		while(scanf(" (%c,%c)",&from[E],&to[E])==2)
			E++;
		//scan in vertices
		V=0;
		scanf("%s");
		scanf(" %c",&t);
		m[t]=V;
		V++;
		while(scanf(",%c",&t)==1){
			m[t]=V;
			V++;
		}
		//UFDS
		UnionFind* U=new UnionFind(V);
		for(int i=0;i<E;i++)
			U->unionSet(m[from[i]],m[to[i]]);
		acorns=U->getSingles();
		trees=(U->getSets())-acorns;
		printf("There are %d tree(s)  and %d acorn(s).\n",trees,acorns);
	}
	return 0;
}

Code: Select all

1
(A,B)
(A,C)
...
(A,V)
****
A,B,C,...,Z

Code: Select all

1
(A,B)
(A,C)
...
(A,W)
****
A,B,C,...,Z