POJ 2513 Colored Sticks

\(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;
}