大发体育娱乐在线-大发体育娱乐官方网站-大发体育娱乐登录网址
做最好的网站

单词接龙,poj2337欧拉路线

来源:http://www.dfwstonefabricators.com 作者:大发体育网络 人气:95 发布时间:2019-11-15
摘要:poj2337 欧拉路线,poj2337欧拉路线 poj2337 那道题前些天上午起首做,前几天才A。不过难题想透了, 开采实际没那么难 题目大要:  给您有的单词,借使一个单词的最终字符与另三个单词

poj2337 欧拉路线,poj2337欧拉路线

poj2337

那道题前些天上午起首做,前几天才A。不过难题想透了, 开采实际没那么难

题目大要: 
给您有的单词,借使一个单词的最终字符与另三个单词首字符相仿,则多个的单词能够连接。问是否能够把全体单词连接起来,並且各个单词只可以用壹回。 
分析: 
能够把各样单词看成是一条边,单词的来踪去迹字符看做是八个不断的点。大家得以把它看做有向图的欧拉路线难点(欧拉路线,欧拉回路不太理解的大团结百度呢)。 
一个有向图含有欧拉通路,首先图是联网的,并且当且仅当该图全部终端的入度 =出度, 恐怕开端极点入度 = 出度 - 1 ,甘休点 出度=入度-1, 其他点入度= 出度。领会了那么些,大家的思绪也就明明白白啦! 
重大来啦:首先剖断图是或不是衔接的,在认清图是还是不是留存欧拉路线,若是都密密匝匝那就找渠道。

 

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
#include<algorithm>
using namespace std;

int out[30], in[30], step[1005], pre[30];
int n, k, t, st;
char w[25];

struct Edge//结构体:边, 存储了边的起点(首字符)和终点(尾字符),状态(是否走过)
{
    int s, e, v;
    char c[25];
}edge[1005];

bool cmp(Edge x, Edge y)
{
    return strcmp(x.c, y.c) < 0 ? true : false;
}
int find(int x)//查找其父节点
{
    if(pre[x] != x)
        pre[x] = find(pre[x]);
    return pre[x];
}
int panduan()//判断是否图是连通的
{
    int fx = find(edge[1].s);
    for(int i = 1; i <= 26; i++)
    {
        if(out[i] > 0 || in[i] > 0)
        {
            if(find(i) != fx)
                return 0;
        }
    }
    return 1;
}
void path(int en)//查找路径
{
    for(int i = 1; i <= n; i++)
    {
        if(edge[i].v == 0 && edge[i].s == en)
        {
            edge[i].v = 1;
            path(edge[i].e);
            step[++k] = i;
        }
    }
}
int main()
{
    cin >> t;
    while(t--)
    {
        memset(out, 0, sizeof(out));
        memset(in, 0, sizeof(in));
        memset(step, 0, sizeof(step));
        for(int i = 1; i <= 30; i++)
            pre[i] = i;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            cin >> w;
            int len = strlen(w);
            int s = w[0] - 'a' + 1;
            int e = w[len - 1] - 'a' + 1;
            edge[i].s = s;
            edge[i].e = e;
            strcpy(edge[i].c, w);
            edge[i].v = 0;

            out[s]++;
            in[e]++;
            /*如果存在欧拉路径,那么所有的点一定都连通.所有的点都在一个集合里,可以用并查集知识
            将所有连接的点并到一起。*/
            int fx = find(s);
            int fy = find(e);
            if(fx != fy)
                pre[fx] = fy;
        }
        sort(edge + 1, edge + 1 + n, cmp);//题目要求字典序最小输出,就先按从小到大的顺序把边(单词)排好
        /*st代表的是路径起点,在这里进行st = edge[1].s赋值,是应为存在两种情况:1.存在一定点出度>入度,
        这个点是起点。2.所有点出度= 入度, 那么从任意一点出发都可以, 为了保证字典序最小, 就从第一个单词开始*/
        st = edge[1].s;
        int i, c1 = 0, c2 = 0;
        for(i = 1; i <= 26; i++)//判断是否有欧拉回路
        {
            if(out[i] == in[i])continue;
            else if(in[i] == out[i] - 1) {c1++; st = i;}//起点
            else if(in[i] == out[i] + 1) c2++;
            else break;
        }
        //如果符合了连通图,并且存在欧拉通路, 就开始找路径
        if(i == 27 && ((c1 == c2 && c1 == 1) || (c1 == c2 && c1 == 0)) && panduan() == 1)
        {
            k = 0;
            path(st);
            for(int i = n; i > 1; i--)//输出这注意点,因为是递归求的路径, 最先得到的是最后的边
                printf("%s.", edge[step[i]].c);
            printf("%sn", edge[step[1]].c);
        }
        else
            printf("***n");
    }
    return 0;
}

 

欧拉路线,poj2337欧拉路径 poj2337 那道题明日中午起初做,明日才A。可是难题想透了, 发现其实没那么难点目概况: 给您有的单词,...

Lamb刚发轫攻读意大利语单词,对单词排序很感兴趣。假诺给Lamb生龙活虎组单词,他能够急速分明是还是不是足以将这一个单词排列在一个列表中,使得该列表中其余单词的首字母与前大器晚成单词的尾字母相像。你能编写叁个程序来帮忙拉姆进行剖断吗?

输入描述:
输入蕴含多组测验数据。对于每组测验数据,第风度翩翩作为一个正整数n,代表有n个单词。然后有n个字符串,代表n个单词。保险:2<=n<=200,各种单词长度超越1且低于等于10,且全部单词都以由小写字母组成。
输出描述:
对于每组数据,输出"Yes"或"No"

输入例子1:
3
abc
cdefg
ghijkl
出口例子1:
Yes

输入例子2:
4
abc
cdef
fghijk
xyz
输出例子2:
No

由题意可以预知,对于输入单词的次第大家是足以调动的,也正是说任由怎么调解单词的生龙活虎风流倜傥,只要能产生接龙就可以

或是有人会想到通过调治单词的逐大器晚成,比方按首字母或尾字母对输入的单词进行重新排序再逐生龙活虎检查首尾是还是不是能够产生接龙,那样就掉入了宗旨的率先个骗局。事实上,在宗旨中叁十三个希腊语字母是没有所谓的前后相继顺序的,因为我们要咬定的是这一个单词能不可能产生一条接龙,固然你的首字母是a而笔者的首字母是z,不过你的单词是abc中而本身的是单词zxa,你的单词依旧排在小编的前面。

此地有人恐怕早已看出来了,借使把各类单词看成一条有向边,首尾字母看成边上的起源和终极,难题就转产生了推断三个有向图是还是不是可以代表为一条(不闭合的卡塔 尔(英语:State of Qatar)欧拉路线或欧拉回路的一笔画难题。

借助有向图中欧拉路线的论肯定理
  一个连通的有向图能够表示为一条从起点到巅峰的(不闭合的卡塔尔欧拉路线的充要条件是: 起源的出度比入度多1, 终点的入度比出度多1,而别的顶点的入度和出度都等于。
  一个连通的有向图能够表示为一条欧拉回路的充要条件是:每种终端的入度和出度都相当

留心到下边笔者对连通的三个字张开了加粗,目标是重申不要忘记记剖断有向图的连通性(这里只要满意弱连通就可以卡塔尔国,对于百度那道笔试题英特网海人民广播电视台大人只思忖到计算点的入度与出度来判断是或不是能造成接龙,而并未有核算有向图的连通性,固然那样的代码能透过牛客OJ上具有的测验用例,但实际对于aba,cdc,efe那样的输入却会赢得错误的输出"Yes",原因正是这个单词产生的有向图是不连贯的。那也从左侧印证了牛客OJ上用例设计的缺乏完美。
源码如下:

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main 
{

    public static void main(String[] args) 
    {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext())
        {
            int n = scan.nextInt();
            String[] arr = new String[n];
            for(int i = 0; i < n ; i++)
                arr[i] = scan.next();
            System.out.println(WordListOrder.canArrangeWords(n, arr));
        }
        scan.close();
    }

}

class WordListOrder {

    public static String canArrangeWords(int n, String[] arr)
    {
        // 26个英文字母看作26个点,用整数0-25来表示
        int[][] directedGraph = new int [26][26];// 邻接矩阵表示有向图
        int[] inDegree = new int [26];           // 顶点入度
        int[] outDegree = new int [26];          // 顶点出度
        boolean[] hasLetter = new boolean[26];   // 标记字母是否出现过
        boolean hasEuler = false;                 // 有狭义欧拉路径或欧拉回路标志
        for(int i = 0; i < n; i++)
        {
            String word = arr[i];
            char firstLetter = word.charAt(0);
            char lastLetter = word.charAt(word.length()-1);
            outDegree[firstLetter - 'a']++;
            inDegree[lastLetter - 'a']++;
            directedGraph[firstLetter - 'a'][lastLetter - 'a'] = 1; // 有向图
            hasLetter[firstLetter - 'a'] = true;
            hasLetter[lastLetter - 'a'] = true;
        }
        int startNum = 0;        
        int endNum = 0;
        for (int vertex = 0; vertex < 26; vertex++)
        {
            if(outDegree[vertex] - inDegree[vertex] == 1)    // 起点
                startNum++;                    
            if(inDegree[vertex] - outDegree[vertex] == 1)    // 终点
                endNum++;
            if(Math.abs(inDegree[vertex] - outDegree[vertex]) > 1)
            {
                hasEuler = false;
                break;
            }
        }
        boolean isEulerPath = (startNum == 1 && endNum == 1);   // 这里指狭义上的欧拉路径,不包括欧拉回路
        boolean isEulerCircuit = (startNum == 0 && endNum == 0);// 欧拉回路
        if((!isEulerPath) && (!isEulerCircuit))    // 既不是欧拉路径也不是欧拉回路
            hasEuler = false;
        // 判断是否弱连通
        int vertexNum = 0;    // 统计图中点的个数
        for(int letter = 0; letter < 26; letter++)
        {
            if(hasLetter[letter])    
                vertexNum++;
        }
        int firstWordFirstLetter = arr[0].charAt(0) - 'a';// 以第一个单词的首字母作为起点进行BFS
        hasEuler = hasEuler && isConnected(firstWordFirstLetter, vertexNum, directedGraph);
        if(hasEuler)
            return "Yes";
        else
            return "No";
    }

    // 判断有向图是否弱连通,即转换成无向图判断是否连通
    public static boolean isConnected(int start, int vertexNum, int[][] directedGraph)
    {
        int[][] undirectedGraph = new int[26][26];
        for(int i = 0; i < 26; i++)     // 把有向图转换成无向图
        {
            for(int j = 0; j < 26; j++) 
            {
                if(directedGraph[i][j] == 1)
                {
                    undirectedGraph[i][j] = 1;
                    undirectedGraph[j][i] = 1;
                }
            }
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        boolean[] passedVertex = new boolean[26];
        int passedVertexNum = 0;
        queue.offer(start);
        // 从起点开始进行BFS,统计遍历到点的个数
        while(!queue.isEmpty())
        {
            int currentVertex = queue.poll();
            passedVertex[currentVertex] = true;
            passedVertexNum++;
            for(int vertex = 0; vertex < 26; vertex++)
            {
                if(undirectedGraph[currentVertex][vertex] == 1 && passedVertex[vertex] == false)
                    queue.offer(vertex);
            }
        }
        // 遍历到所有的点,证明无向图是连通的
        if(passedVertexNum == vertexNum)
            return true;
        else 
            return false;
    }
}

本文由大发体育娱乐在线发布于大发体育网络,转载请注明出处:单词接龙,poj2337欧拉路线

关键词:

上一篇:auto类型说明符

下一篇:没有了

频道精选

最火资讯