题解 P1333 【瑞瑞的木棍】

· · 题解

主要的算法是欧拉路。

题目要求每条木棍都用过，同颜色的两端可以相接，如果没有字符串处理，几乎是一道欧拉路的模板题

把每种颜色看做一个点，木棍看做连接两种颜色的无向边，整个问题就转化成了求这个图是否存在欧拉路。

对于点的编号，可以采用字典树或者用STL里的unordered_map（map会超时）。重要：建议不选STL,非常慢……

接下来就是欧拉路的判定。

首先图必须是联通的。楼下给出了用dfs的方法，这里给出用并查集的方法。

对于所有的点建立一个并查集。对于每条边，尝试把它两端的点合并，并记录有效合并（即合并前两个点不在同一组中）的次数。

设点（注意不是边）的数量为N，有效合并次数为M，则当且仅当M==N-1时图是联通的。下面给出简单说明：

如果图是联通图，并查集就只有一个组。而初始有N个组，每次有效合并会减少一个组，最后只剩一个组，所以有效合并次数M=N-1。

其次（也是最后），图中奇数度数的点的个数必须为0（最后回到出发点）或2（一个点出发，另一个点结束）。对此，输入时记录每个点度数，最后全部扫一遍即可。

代码

核心部分代码如下：

#include <stdio.h>
#define N 500010//题目中说最多有250000条边，也就是最多有500000个点
int n=0,deg[N];char s[15];//n:点数（颜色数）,deg:每个点度数
/*求编号部分(getid)*/
//...
/*并查集*/
int fa[N];
inline int find(int a) {
    return fa[a]?fa[a]=find(fa[a]):a;
}
inline bool join(int a,int b) {//有效合并返回true,无效返回false 
    int x=find(a),y=find(b);
    if(x==y) return false;
    fa[x]=y;return true;
}
/********************/
inline bool check() {
    int x,y,cnt=0;
    while(~scanf("%s",s)) {
        x=getid(s);
        scanf("%s",s);
        y=getid(s);//getid求编号 
        if(join(x,y)) ++cnt;//记录有效合并次数 
        ++deg[x];++deg[y];//统计度数 
    }
    if(cnt<n-1) return false;//判联通:只有当cnt==n-1时是联通的 
    cnt=0;//记录奇数度点的个数
    for(int i=1;i<=n;++i) if((deg[i]&1)&&++cnt>2) return false;//扫一遍颜色的度,奇数度点个数>2就退出 
    return true;
}
int main() {
    puts(check()?"Possible":"Impossible");
    return 0;
}

求编号的部分(两种做法)：

/*1.Trie/字典树*/
int nd=1,root=1;struct node{int son[26],num;}t[1000010];
int getid(const char *s) {
    int k=root;char c;
    for(int i=0;s[i];++i) {
        c=s[i]-'a';
        if(!t[k].son[c]) t[k].son[c]=++nd;//动态开点
        k=t[k].son[c];
    }
    if(!t[k].num) t[k].num=++n;
    return t[k].num;
}
/*2.unordered_map*/
#include <string>
#include <unordered_map>
using namespace std;
unordered_map<string,int> M;
int getid(const char *s) {
    return M[s]?M[s]:M[s]=++n;
}