python/TangDou/AcWing/EulerPath/POJ2513_1.cpp

#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 500010;
char s1[15], s2[15]; // 两个字符串

// POJ只能使用map, 不能使用unordered_map,而map性能很差，代码非常可能TLE，我尝试修改为链式前向星，结果TLE了
map<string, int> _map;
vector<int> g[N];
int id, st[N], d[N];

int cnt;
void dfs(int u) {
    cnt++;
    st[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (st[v]) continue;
        dfs(v);
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ2513.in", "r", stdin);
#endif

    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];
        // 邻接表走起
        g[a].push_back(b), g[b].push_back(a);
        // 记录度
        d[a]++, d[b]++;
    }
    // 大家小心，这题有空数据的情况，应输出possible！
    if (id == 0) {
        puts("Possible");
        return 0;
    }

    dfs(1); // 判断有没有孤立点
    if (cnt != id) {
        puts("Impossible");
        return 0;
    }

    cnt = 0;
    for (int i = 1; i <= id; i++) // 无向图有0个或两个奇度点含有
        if (d[i] % 2) cnt++;      // 欧拉回路或欧拉通路

    if (cnt == 0 || cnt == 2) // 好像有点卡常，交c++冲过去了...
        puts("Possible");
    else
        puts("Impossible");
    return 0;
}