poj2513

maksyuki 发表于 oj 分类，标签: 图论-欧拉回路

15 9月 2015

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?

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.

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible

Hint

Huge input,scanf is recommended.

Source

The UofA Local 2000.10.14

题目类型：无向图欧拉回路(路径)的判定

算法分析：将颜色看成节点，连接颜色的木棒看成一条无向边。使用并查集判断构建的图中是否连通，然后统计每一个节点的奇数度数的个数，直接使用欧拉路径和回路的判断定理判断即可。注意需要使用trie树或者是hash表进行字符串的快速检索和插入，直接使用O(n)的算法会超时。注意数据中可能出现自环，即代码中的id可能最小取值到0，所以在判断连通性时下标需要从0开始！！！下面会给出使用Trie树实现的代码

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const int maxn = 500000 + 666;

int len = 0;
char ans[maxn][16],val_a[16], val_b[16];
int parent[maxn], deg[maxn];

struct Node
{
    int id;
    char s[16];
};

vector <Node> vec[maxn];

unsigned int BKDRHash (char *val)
{
    unsigned int seed = 131, hash_val = 0;
    while (*val)
    {
        hash_val = hash_val * seed + (*val++);
    }

return hash_val % maxn;
}


int Get (char *val)
{
    int key = BKDRHash (val), i;
    for (i = 0; i < vec[key].size (); i++)
        if (!strcmp (val, vec[key][i].s))
            return vec[key][i].id;

    Node temp;
    strcpy (temp.s, val);
    temp.id = len++;
    vec[key].push_back (temp);

return temp.id;
}

int UnFind (int val)
{
    if (parent[val] == val)
        return val;

return parent[val] = UnFind (parent[val]);
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    memset (deg, 0, sizeof (deg));
    int i;
    for (i = 0; i < maxn; i++)
        parent[i] = i;


    while (scanf ("%s%s", val_a, val_b) != EOF)
    {
        int u = Get (val_a);
        int v = Get (val_b);
        deg[u]++;
        deg[v]++;

        if (UnFind (u) != UnFind (v))
            parent[UnFind(u)] = UnFind (v);
    }

    int odd = 0;
    for (i = 0; i < len; i++)
    {
        if (deg[i] % 2)
            odd++;
    }

    bool is_valid = true;
    int temp = UnFind (0);

    for (i = 0; i < len; i++)
        if (temp != UnFind (i))
        {
            is_valid = false;
            break;
        }


    if ((odd == 0 || odd == 2) && is_valid)
        printf ("Possible\n");

    else
        printf ("Impossible\n");

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const int maxn = 500000 + 666;

int len = 0;

char ans[maxn][16],val_a[16], val_b[16];

int parent[maxn], deg[maxn];

struct Node

{

int id;

char s[16];

};

vector <Node> vec[maxn];

unsigned int BKDRHash (char *val)

{

unsigned int seed = 131, hash_val = 0;

while (*val)

{

hash_val = hash_val * seed + (*val++);

}

return hash_val % maxn;

}

int Get (char *val)

{

int key = BKDRHash (val), i;

for (i = 0; i < vec[key].size (); i++)

if (!strcmp (val, vec[key][i].s))

return vec[key][i].id;

Node temp;

strcpy (temp.s, val);

temp.id = len++;

vec[key].push_back (temp);

return temp.id;

}

int UnFind (int val)

{

if (parent[val] == val)

return val;

return parent[val] = UnFind (parent[val]);

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

memset (deg, 0, sizeof (deg));

int i;

for (i = 0; i < maxn; i++)

parent[i] = i;

while (scanf ("%s%s", val_a, val_b) != EOF)

{

int u = Get (val_a);

int v = Get (val_b);

deg[u]++;

deg[v]++;

if (UnFind (u) != UnFind (v))

parent[UnFind(u)] = UnFind (v);

}

int odd = 0;

for (i = 0; i < len; i++)

{

if (deg[i] % 2)

odd++;

}

bool is_valid = true;

int temp = UnFind (0);

for (i = 0; i < len; i++)

if (temp != UnFind (i))

{

is_valid = false;

break;

}

if ((odd == 0 || odd == 2) && is_valid)

printf ("Possible\n");

else

printf ("Impossible\n");

return 0;

}

//注意数据中可能出现自环，即代码中的id可能最小取值到0，所以在判断连通性时下标需要从0开始！！！
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 26;
const int nodemaxn = 500000 + 66;

int id, aacnt[nodemaxn], parent[nodemaxn];

struct Trie
{
    int Next[nodemaxn][maxn], last[nodemaxn];
	int len, root;

    int newnode ()
    {
        for (int i = 0; i < maxn;i++)
            Next[len][i] = -1;
        last[len] = -1;
        len++;
        return len - 1;
    }

    void Init ()
    {
    	len = 0;
    	root = newnode ();
    }

    void Insert (char *s, int vv)
    {
        int p = root;
        for (int i = 0; s[i]; i++)
		{
            if (Next[p][s[i]-'a'] == -1)
				Next[p][s[i]-'a'] = newnode ();

			p = Next[p][s[i]-'a'];
		}
        last[p] = vv;
    }

    int Query (char *s)
    {
//    	cout << s << endl;
        int p = root;
        for (int i = 0; s[i]; i++)
		{
            if (Next[p][s[i]-'a'] == -1)
				return -1;

			p = Next[p][s[i]-'a'];
		}

		if (last[p] != -1)
			return last[p];

		return -1;
    }
};

Trie aa;

int UnFind (int val)
{
	if  (parent[val] == val)
		return val;

	return parent[val] = UnFind (parent[val]);
}

int main()
{
//	ifstream cin("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

    char sa[66], sb[66];
    aa.Init ();

	id = 0;
	memset (aacnt, 0, sizeof (aacnt));
	for (int i = 0; i < nodemaxn; i++)
		parent[i] = i;

	int pp, va, vb;
    while (scanf ("%s%s", sa, sb) != EOF)
	{
        pp = aa.Query (sa);

        if (pp == -1)
		{
			aa.Insert (sa, id);
            aacnt[id]++;
            va = id;
            id++;
		}

		else
		{
			aacnt[pp]++;
			va = pp;
		}

		pp = aa.Query(sb);
		if (pp == -1)
		{
			aa.Insert (sb, id);
            aacnt[id]++;
            vb = id;
            id++;
		}

		else
		{
			aacnt[pp]++;
			vb = pp;
		}

		if (UnFind (va) != UnFind (vb))
			parent[UnFind(va)] = UnFind (vb);
	}

//	for (int i = 0; i < id; i++)
//		cout << aacnt[i] << endl;

    int odd = 0;
    for (int i = 0; i < id; i++)
        if (aacnt[i] & 1)
			odd++;

	bool is_valid = true;

	int tt = UnFind (0);
	for (int i = 0; i < id; i++)
        if (UnFind (i) != tt)
		{
			is_valid = false;
			break;
		}

	if ((odd == 0 || odd == 2) && is_valid)
		puts ("Possible");

	else
		puts ("Impossible");

return 0;
}

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

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

//注意数据中可能出现自环，即代码中的id可能最小取值到0，所以在判断连通性时下标需要从0开始！！！

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 26;

const int nodemaxn = 500000 + 66;

int id, aacnt[nodemaxn], parent[nodemaxn];

struct Trie

{

int Next[nodemaxn][maxn], last[nodemaxn];

int len, root;

int newnode ()

{

for (int i = 0; i < maxn;i++)

Next[len][i] = -1;

last[len] = -1;

len++;

return len - 1;

}

void Init ()

{

len = 0;

root = newnode ();

}

void Insert (char *s, int vv)

{

int p = root;

for (int i = 0; s[i]; i++)

{

if (Next[p][s[i]-'a'] == -1)

Next[p][s[i]-'a'] = newnode ();

p = Next[p][s[i]-'a'];

}

last[p] = vv;

}

int Query (char *s)

{

// cout << s << endl;

int p = root;

for (int i = 0; s[i]; i++)

{

if (Next[p][s[i]-'a'] == -1)

return -1;

p = Next[p][s[i]-'a'];

}

if (last[p] != -1)

return last[p];

return -1;

}

};

Trie aa;

int UnFind (int val)

{

if (parent[val] == val)

return val;

return parent[val] = UnFind (parent[val]);

}

int main()

{

// ifstream cin("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

char sa[66], sb[66];

aa.Init ();

id = 0;

memset (aacnt, 0, sizeof (aacnt));

for (int i = 0; i < nodemaxn; i++)

parent[i] = i;

int pp, va, vb;

while (scanf ("%s%s", sa, sb) != EOF)

{

pp = aa.Query (sa);

if (pp == -1)

{

aa.Insert (sa, id);

aacnt[id]++;

va = id;

id++;

}

else

{

aacnt[pp]++;

va = pp;

}

pp = aa.Query(sb);

if (pp == -1)

{

aa.Insert (sb, id);

aacnt[id]++;

vb = id;

id++;

}

else

{

aacnt[pp]++;

vb = pp;

}

if (UnFind (va) != UnFind (vb))

parent[UnFind(va)] = UnFind (vb);

}

// for (int i = 0; i < id; i++)

// cout << aacnt[i] << endl;

int odd = 0;

for (int i = 0; i < id; i++)

if (aacnt[i] & 1)

odd++;

bool is_valid = true;

int tt = UnFind (0);

for (int i = 0; i < id; i++)

if (UnFind (i) != tt)

{

is_valid = false;

break;

}

if ((odd == 0 || odd == 2) && is_valid)

puts ("Possible");

else

puts ("Impossible");

return 0;

}

poj2480

poj2528

超客的水墨烟雨

poj2513

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	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