UVa 540 - Team Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

//union_set
int sets[1000001];  
int rank[1000001];  
  
void set_inital(int a, int b)  
{  
    for (int i = a; i <= b; ++ i) {  
        rank[i] = 0;  
        sets[i] = i;  
    }  
}  
  
int set_find(int a)  
{  
    if (a != sets[a])  
        sets[a] = set_find(sets[a]);  
    return sets[a];  
}  
  
void set_union(int a, int b)  
{  
    if (rank[a] < rank[b])  
        sets[a] = b;  
    else {  
        if (rank[a] == rank[b])  
            rank[a] ++;  
        sets[b] = a;  
    }  
}  
//end_union_set  

//multilevel_queue
typedef struct _queuelist
{
	int first, last;
	int value;
	int next;
}queuelist;
queuelist mlList[10001], mlRoot;

typedef struct _queuenode
{
	int value;
	int next;
}queuenode;
queuenode mlNode[1000001];

int hashlist[1000001];
int mlnodesize;
int mllistsize;

void mlqueue_iniital()
{
	memset(hashlist, -1, sizeof(hashlist));
	memset(mlList, 0, sizeof(mlList));
	memset(mlNode, 0, sizeof(mlNode));
	mlnodesize = 1;
	mllistsize = 1;
	mlRoot.first = mlRoot.last = 0;
}

void mlqueue_enqueue(int id, int value)
{
	if (hashlist[id] == -1) {//不存在同类，创建对应的链表，放在链表列的最后并
		hashlist[id] = mllistsize;
		mlList[hashlist[id]].first = mlnodesize;
		mlList[mlRoot.last].next = mllistsize;
		mlRoot.last = mllistsize ++;
		mlList[mlRoot.last].value = id;
		if (mlRoot.first == 0)//第一个节点 
			mlRoot.first = mlRoot.last;
	}
	//已存在同类，插入对应的链表末端 
	int ListIndex = hashlist[id];
	mlNode[mlnodesize].value = value;
	mlNode[mlList[ListIndex].last].next = mlnodesize;
	mlList[ListIndex].last = mlnodesize ++;
}

int mlqueue_dequeue()
{
	//没有元素 
	if (mlRoot.first == 0) return -1;
	//删除第一个链表的第一个元素 
	int ListIndex = mlRoot.first;
	int value = mlNode[mlList[ListIndex].first].value;
	mlList[ListIndex].first = mlNode[mlList[ListIndex].first].next;
	//链表只有一个元素，删除链表 
	if (mlList[ListIndex].first == 0) {
		hashlist[mlList[ListIndex].value] = -1;
		mlRoot.first = mlList[mlRoot.first].next;
		//唯一元素，清空队列的链表 
		if (mlRoot.first == 0) {
			mlRoot.last = 0;
		}
	}
	return value;
}
//end_multilevel_queue 

int main()
{
	int cases = 1, t, m;//read team queue
	while (~scanf("%d",&t) && t) {
		//read data
		int buf[1001];
		set_inital(0, 999999);
		while (t --) {
			scanf("%d%d",&m,&buf[0]);
			for (int i = 1; i < m; ++ i) {
				scanf("%d",&buf[i]);
			}
			for (int i = 1; i < m; ++ i) {
				set_union(set_find(buf[0]), set_find(buf[i]));
			}
		}
		
		//deal data
		int  id;
		char command[20];
		mlqueue_iniital();
		printf("Scenario #%dn",cases ++);
		while (~scanf("%s",command) && strcmp(command, "STOP")) {
			if (!strcmp(command, "ENQUEUE")) {
				scanf("%d",&id);
				mlqueue_enqueue(set_find(id), id);
			}
			if (!strcmp(command, "DEQUEUE")) {
				printf("%dn",mlqueue_dequeue());
			}
		}
		puts("");
	}
    return 0;
}