[POJ]2513 Colored Sticks

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

如果我们把不同的颜色看做顶点，对于一条stick，我们把两端的颜色对应的顶点连上边。这道题就是要我们找有没有一条路径只经过所有边一次，这就是欧拉路径的问题。我们在这一篇文章讲过，一个图存在欧拉路径的充要条件是：

• 图是联通的
• 度数为奇数的点为2，其余度数均为偶数

所以在这里我们只需要检查图的这两个性质。鉴于输入的数据量很大，我们用Trie来统计每个颜色节点的度数，Union Find可以帮助我们检查图的联通性。时间复杂度 O(N), N为stick的数量。代码如下：

	//2513
	/*
	You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
	Input
	Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.
	Output
	If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.
	*/
	#include <cstdio>
	#include <cstring>
	#include <vector>
	using namespace std;
	const int MAXN = 500005;
	const int MAXL = 15;
	int colors[MAXN];
	int cnt;
	struct Node
	{
	Node* children[26];
	int id;
	Node()
	{
	memset(children, 0, sizeof(children));
	id = -1;
	}
	};
	class Trie
	{
	public:
	Trie()
	{
	root = new Node();
	}
	~Trie()
	{
	clear(root);
	}
	int insert(char* s)
	{
	Node* curr = root;
	int len = strlen(s);
	for(int i = 0; i < len; ++i)
	{
	int idx = s[i] - 'a';
	if(!curr->children[idx])
	curr->children[idx] = new Node();
	curr = curr->children[idx];
	}
	if(curr->id == -1)//if it is a new color
	curr->id = cnt++;
	++colors[curr->id];
	return curr->id;
	}
	private:
	Node* root;
	void clear(Node* curr)
	{
	if(!curr)return;
	for(int i = 0; i < 26; ++i)
	clear(curr->children[i]);
	delete curr;
	}
	};
	class UnionFind
	{
	public:
	UnionFind(int n)
	{
	m_uf = vector<int>(n, 0);
	m_sz = vector<int>(n, 1);
	for(int i = 0; i < n; ++i)
	m_uf[i] = i;
	}
	void connect(int i, int j)
	{
	int rootI = root(i), rootJ = root(j);
	if(rootI == rootJ)return;
	if (m_sz[rootI] <= m_sz[rootJ])
	{
	m_uf[rootI] = rootJ;
	m_sz[rootJ] += m_sz[rootI];
	}
	else
	{
	m_uf[rootJ] = rootI;
	m_sz[rootI] += m_sz[rootJ];
	}
	}
	bool find(int i, int j)
	{
	return root(i) == root(j);
	}
	private:
	vector<int> m_uf;
	vector<int> m_sz;
	int root(int i)
	{
	if (m_uf[i] == i)return i;
	int r = root(m_uf[i]);
	m_uf[i] = r;
	return r;
	}
	};
	bool hasEulerPath(UnionFind& uf)
	{
	//if we have no stick return ture
	if(!cnt)return true;
	//make sure graph is connected
	for(int i = 1; i < cnt; ++i)
	if(!uf.find(0, i))return false;
	//make sure # of nodes with odd degree is 2 or 0
	int odd = 0;
	for(int i = 0; i < cnt; ++i)
	if(colors[i] % 2)++odd;
	return !odd || odd == 2;
	}
	int main()
	{
	cnt = 0;
	char A[MAXL], B[MAXL];
	Trie trie;
	UnionFind uf(MAXN);
	memset(colors, 0, sizeof(colors));
	while(~scanf("%s%s", A, B))
	{
	int idA = trie.insert(A), idB = trie.insert(B);
	uf.connect(idA, idB);
	}
	puts(hasEulerPath(uf) ? "Possible" : "Impossible");
	return 0;
	}

view raw POJ_2513_Colored Sticks.cpp hosted with ❤ by GitHub