\(POJ\) \(2513\) \(Colored\) \(Sticks\)
一、题目描述
一堆木棍左右两端涂有颜色,相同颜色的可以连接在一起，问所有木棍能否都连上
二、解题代码
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
// 无法AC,TLE，原因不明白
using namespace std;
const int N = 250010, M = 500010;
char s1[15], s2[15]; // 两个字符串
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int cnt;
map<string, int> _map;
int id = 1, st[N], d[N];
void dfs(int u) {
cnt++; // cnt是数量统计器
st[u] = 1; // 标识被访问过
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (st[v]) continue;
dfs(v);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("POJ2513.in", "r", stdin);
#endif
memset(h, -1, sizeof h);
int op;
while (~scanf("%s%s", s1, s2)) {
int a, b;
if (!_map[s1]) _map[s1] = id++; // 手动离散化，帅！
if (!_map[s2]) _map[s2] = id++;
a = _map[s1], b = _map[s2];
// 邻接表走起
add(a, b), add(b, a);
// 记录度
d[a]++, d[b]++;
}
// 只有1个点
if (id == 1) {
puts("Possible");
return 0;
}
dfs(1); // 判断有没有孤立点
if (cnt != id - 1) {
puts("Impossible");
return 0;
}
op = 0;
for (int i = 1; i < id; i++) // 无向图有0个或两个奇度点含有
if (d[i] % 2) op++; // 欧拉回路或欧拉通路
if (op == 0 || op == 2) // 好像有点卡常，交c++冲过去了...
puts("Possible");
else
puts("Impossible");
return 0;
}