【大明王朝】

题目描述

五行学说认为宇宙是由金、木、水、火、土五种最基本物质构成的,宇宙中各种事物和现象(包括人在内)的发展、变化都是这五种不同属性的物质不断运动和相互作用的结果。
五行学说认为,事物与事物之间存在着一种联系,这种联系又促进着事物的发展变化。五行之间存在着相生相克的规律。
相生:含有互相滋生,促进助长的意思。
相克:含有互相制约、克制和抑制的意思。
五行相生:木生火,火生土,土生金,金生水,水生木。
五行相克:木克土,土克水,水克火,火克金,金克木。

1368年朱元璋赢得了战争并建立了大明王朝。此时全国分布有很多城市,每个城市都有属于自己的五行之一的元素(用图示的英文单词表示),并且已经存在一些连接城市的道路。朱元璋想把整个国家的城市划分到几个省里面,制定以下重建规则:
(1)省的个数尽量少;
(2)在同一个省中,任意两个城市可以相互到达(某些省份可能只有一个城市);
另外依据五行原理,还要求:
(1)如果有一条道路连接城市A和城市B,并且按五行相克原理,城市A“克”城市B,则这条道路必须被取消;
(2)如果有一条道路连接城市A和城市B,并且按五行相生原理,城市A“生”城市B,则这条道路作为从A指向B的有向道路被使用。
(3)如果城市A和城市B既不相克,也不相生,则这条道路作为无向道路继续保留。
现在,我们有了一张全国的城市分布图,请你计算重建后,最少可以建立几个省份。

输入格式

第一行有两个整数 N(N≤100)和 M(M≤1000)。N 是城市的数量,M 是重建前的原始道路的数量。城市的编号为 0,1,2,……,N-1。
接下来有 N 行,每行分别表示城市 0,城市 1,……,城市 N-1 所属于的五行元素(单词表示)。
接下来有 M 行,每行两个整数 A 和 B(0≤A,B≤N-1),表示在重建前有一条原始的道路连接城市 A 和城市 B 。

输出格式

输出一个整数,即最少的省份数量。

样例数据 1

输入

5 8

Ground
Fire
Water
Wood
Gold
0 1
0 2
0 3
0 4
1 4
4 2
2 3
3 1

输出

1

这道题奇葩了,直接string读入再建边只能A7个点,而换成读前2个字母再把对应元素标号的方式却可以全A,我并不知道这两种方法有什么区别……然而一天后我发现判断双向边时我的最后一句else仅仅对应最后一个if相当于边可能被建2次, 就这样悲惨的WA了…… 所以说考试马虎不得啊!总之就是一道裸的Tarjan题,下面是代码

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*