UVa 10129 Play on Words


好久不写代码果然手会生成屎

题目在poj上也有


题意就是给你一堆单词,按首位顺序排列起来,问你有没有解。

第一眼看上去是个哈密顿通路,单词当做节点,首尾关系作边,听上去妥妥的不过N有100000 复杂度太恐怖。

其实是从刘汝佳的小白书第二版(其实该叫小紫红书了)上欧拉回路那节看到的,所以得考虑考虑转换

把单词当边,首尾字符当做点 题目就转变为 欧拉通路


不得不感慨,图论算法的重点还是在构图!!!


判断欧拉通路:

1. 一个有向图存在欧拉回路必定也存在欧拉通路...因为通路的定义包括了回路
2. 不考虑为欧拉回路的情况..一个有向图是欧拉通路就必须有一个点出度-入度=1,一个点入度-出度=1..这两点就是欧拉通路的起点和终点..并且该图连通

3. 我自己加一条,其实是对2的理解:入读-出度>1 时直接return false ,排除 a->b a->c 这种情况


判断欧拉回路:

无向图是欧拉图的充要条件是所有点的度为偶数并且所有点联通
有向图是欧拉图的充要条件是所有点的入度=出度..并且联通...


判断连通

1. dfs遍历,这里有一份参考代码不过我一直怀疑其正确性。因为你无法确定有向图的起点,比如 a->b->c 如果你从b点开始搜的话就会悲催,但是你不知道b点上面还有没有点。

2. 并查集,并查集的方便之处不用废话。但是在图论中两点之间有多条边时需要注意一些细节的处理。


关于判断入读出度

一种办法是分别记录 in[] out[]

我用的办法是一个数组:sz[x]++ 表示拉出一条边,sz[x]--表示走来一条边,sz[x]==1 sz[x]==-1 就是上面的两种情况


上代码吧

这是只开sz[]的

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#define N 101010
using namespace std;

int sz[333];
int fa[333];
bool ok[333];   //  数据中使用到的单词
int n, T;

int getfa(int v)
{
    if ( fa[v] == v ) return v;
    return fa[v] = getfa(fa[v]);
}

void init()
{
    memset(ok, 0, sizeof(ok));
    memset(sz, 0, sizeof(sz));
    cin >> n;
    string a;
    for ( int i('a'); i <= 'z'; i++) fa[i] = i;
    for ( int i(1); i <= n; i++)
    {
        cin >> a;
        int x = a[0], y = a[a.size() - 1];
        fa[getfa(x)] = getfa(y);
        ok[x] = ok[y] = true;
        sz[x]++;
        sz[y]--;
    }
}

bool check()
{
    int tf = 0 , i;
    for ( i = 'a'; i <= 'z'; i++)
    {
        if (ok[i])
        {
            if ( !tf ) tf = getfa(i);
            else if ( getfa(i) != tf ) return false;        //  不连通
        }
    }

    int c1 = 0, c2 = 0;
    for ( int i('a'); i <= 'z'; i++)
    {
        if (!ok[i]) continue;
        if ( sz[i] == 0 ) continue;
        else if ( sz[i] == 1 ) c1++;
        else if ( sz[i] == -1) c2++;
        else return false;				//  其它乱七八糟的情况 比如 ab ab out[a]=2 in[b]=2 
    }

    if ( (c1 == 1 && c2 == 1) || (c1 == 0 && c2 == 0) ) //  单向路径 or 回路
        return true;
    else
        return false;
}

int main()
{
    freopen("in.txt", "r", stdin);
    for ( cin >> T; T--; )
    {
        init();
        if (check())
            cout << "Ordering is possible." << endl;
        else
            cout << "The door cannot be opened." << endl;
    }
}


为保险起见,还是开了两个数组的

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#define N 101010
using namespace std;

int in[333], out[333];
int fa[333];
bool ok[333];   //  数据中使用到的单词
int n, T;

int getfa(int v)
{
    if ( fa[v] == v ) return v;
    return fa[v] = getfa(fa[v]);
}

void init()
{
    memset(ok, 0, sizeof(ok));
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    cin >> n;
    string a;
    for ( int i('a'); i <= 'z'; i++) fa[i] = i;
    for ( int i(1); i <= n; i++)
    {
        cin >> a;
        int x = a[0], y = a[a.size() - 1];
        fa[getfa(x)] = getfa(y);
        ok[x] = ok[y] = true;
        out[x]++;
        in[y]++;
    }
}

bool check()
{
    int tf = 0 , i;
    for ( i = 'a'; i <= 'z'; i++)
    {
        if (ok[i])
        {
            if ( !tf ) tf = getfa(i);
            else if ( getfa(i) != tf ) return false;        //  不连通
        }
    }

    int c1 = 0, c2 = 0;
    for ( int i('a'); i <= 'z'; i++)
    {
        if (!ok[i]) continue;
        if ( in[i] == out[i] ) continue;
        else if ( in[i] - out[i] == 1 ) c1++;
        else if ( in[i] - out[i] == -1) c2++;
        else return false;
        //else {printf("%d%d\n",in[i],out[i]);return false;}          //  其它乱七八糟的情况
    }

    if ( (c1 == 1 && c2 == 1) || (c1 == 0 && c2 == 0) ) //  单向路径 or 回路
        return true;
    else
        return false;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    for ( cin >> T; T--; )
    {
        init();
        if (check())
            cout << "Ordering is possible." << endl;
        else
            cout << "The door cannot be opened." << endl;
    }
}





注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-04 23:04
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议