Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Trie + 并查集 + 欧拉回路

Posted by zhouzp15 at 2017-01-20 22:48:16 on Problem 2513
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int N = 250000 * 2 + 2;
const int M = 26;
int degree[N], pa[N];

inline int find(int x)
{
	int boss = x;
	while (pa[boss] != boss) boss = pa[boss];
	
	int pos = x, tmp;
	while (pa[pos] != boss) tmp = pa[pos], pa[pos] = boss, pos = tmp;
	return boss;
}

inline void join(int x, int y)
{
	int boss1 = find(x), boss2 = find(y);
	if (boss1 != boss2) pa[boss2] = boss1;
}

class Trie
{
	struct Node
	{
		bool flag;
		int id;
		Node *ch[M];
	} _tree[10 * N], *_root; 
	int _alloc;
	
	Node *newNode()
	{
		_tree[_alloc].flag = false; _tree[_alloc].id = 0;
		for (int i = 0; i < M; i++) _tree[_alloc].ch[i] = NULL;
		return &(_tree[_alloc++]);
	}
	
public:
	int cnt;
	Trie() : _alloc(0), cnt(0) { _root = newNode(); }
	
	int insert(const char *str)
	{
		Node *now = _root;
		for (int i = 0, len = strlen(str); i < len; i++)
		{
			Node *&child = now->ch[str[i] - 'a'];
			if (!child) child = newNode();
			now = child;
		}
		if (!now->flag) now->flag = true, now->id = cnt++;
		return now->id;
	}
} trie;

int main()
{
	char color1[12], color2[12];
	for (int i = 0; i < N; i++) pa[i] = i;
	
	int idx1, idx2;
	while (scanf("%s %s", color1, color2) == 2)
	{
		idx1 = trie.insert(color1), idx2 = trie.insert(color2);		
		join(idx1, idx2); degree[idx1]++; degree[idx2]++;
	}
	
	int sum = 0;
	for (int i = 0; i < trie.cnt; i++) if (degree[i] & 1) sum++;
	if (sum > 2) { printf("Impossible\n"); return 0; }
	
	int boss = find(0);
	for (int i = 0; i < trie.cnt; i++) if (find(i) != boss) { printf("Impossible\n"); return 0; }
	
	printf("Possible\n");	
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator