o.boj 1501——多彩瓜
注:最近の一連のACMの内容は、2年以上前のコードで、自分で振り返ってみましょう.
Description
dalongのおじさんは最近地方へ旅行に行ったとき、dalongに不思議な果物を持ってきました.多彩な瓜です.この瓜はとてもきれいで、たくさんの層があって、どの層も色です.多彩な瓜は長く置くと悪くなるので、dalongは毎日1層食べることにしましたが、多彩な瓜はたくさんの層があって、毎日1層食べるとまだ多彩な瓜を食べていないと壊れてしまいます.多彩な瓜の色が多いので、dalongはいくつかの近い色を同じ色だと思っています.このように顔の色を合わせると、多彩な瓜は元のような層がありません.dalongは多彩な瓜が壊れる前に食べ終わるよ~oh,yeah.今dalongはあなたに多彩な瓜の最初の各層の色、色の関係を教えて、あなたは彼がこれらの瓜を食べ終わるのに何日かかるかを計算するのを助けることができますか?なお、dalongが色aと色bが同じ色であり、色bと色cが同じ色であると判断した場合、色aと色cも同じ色である.
Input
複数組のデータテストは、各組のデータ入力の最初の行に対して正の整数n(1<=n<=50000)であり、m(1<=m<=100)は多彩な瓜が最初にn層を有し、合計m種の異なる色を示す.2行目にn個の数がある、i番目の数coriは多彩な瓜のi層目の色(1<=cori<=m)を表す.3行目は正の整数k(0<=3000<=k)であり、k群の色に類似した関係があることを示す.後のk行は、行ごとに2つの正の整数a,b(1<=a,b<=m,a!=b)であり、dalongがaとbが同じ色であると考えていることを示す.入力の最後は2つの0で、入力が終わったことを示して、このデータは処理しないでください
Output
各グループのデータに対して、dalongを出力するには数日で多彩な瓜を食べ終わる必要があります.
Sample Input
5 3 1 1 2 3 1 1 1 2 0 0
Sample Output
3
Hint
1と2は同じ色なので、dalongは初日に前の3層(1,1,2)を食べ、翌日に4層(3)を食べ、3日目に最後の層(1)を食べることができます.そのため、多彩な瓜を食べるのに3日かかります.
図の思想から見ると、閉包によって2点が達成できるかどうかを求め、同じ点と見なすことができる.この問題は水より直接floydでいいです.
Description
dalongのおじさんは最近地方へ旅行に行ったとき、dalongに不思議な果物を持ってきました.多彩な瓜です.この瓜はとてもきれいで、たくさんの層があって、どの層も色です.多彩な瓜は長く置くと悪くなるので、dalongは毎日1層食べることにしましたが、多彩な瓜はたくさんの層があって、毎日1層食べるとまだ多彩な瓜を食べていないと壊れてしまいます.多彩な瓜の色が多いので、dalongはいくつかの近い色を同じ色だと思っています.このように顔の色を合わせると、多彩な瓜は元のような層がありません.dalongは多彩な瓜が壊れる前に食べ終わるよ~oh,yeah.今dalongはあなたに多彩な瓜の最初の各層の色、色の関係を教えて、あなたは彼がこれらの瓜を食べ終わるのに何日かかるかを計算するのを助けることができますか?なお、dalongが色aと色bが同じ色であり、色bと色cが同じ色であると判断した場合、色aと色cも同じ色である.
Input
複数組のデータテストは、各組のデータ入力の最初の行に対して正の整数n(1<=n<=50000)であり、m(1<=m<=100)は多彩な瓜が最初にn層を有し、合計m種の異なる色を示す.2行目にn個の数がある、i番目の数coriは多彩な瓜のi層目の色(1<=cori<=m)を表す.3行目は正の整数k(0<=3000<=k)であり、k群の色に類似した関係があることを示す.後のk行は、行ごとに2つの正の整数a,b(1<=a,b<=m,a!=b)であり、dalongがaとbが同じ色であると考えていることを示す.入力の最後は2つの0で、入力が終わったことを示して、このデータは処理しないでください
Output
各グループのデータに対して、dalongを出力するには数日で多彩な瓜を食べ終わる必要があります.
Sample Input
5 3 1 1 2 3 1 1 1 2 0 0
Sample Output
3
Hint
1と2は同じ色なので、dalongは初日に前の3層(1,1,2)を食べ、翌日に4層(3)を食べ、3日目に最後の層(1)を食べることができます.そのため、多彩な瓜を食べるのに3日かかります.
図の思想から見ると、閉包によって2点が達成できるかどうかを求め、同じ点と見なすことができる.この問題は水より直接floydでいいです.
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int G[50050], c[102][102];
int n, m, k, day;
int a, b;
cin >> n >> m;
while (n || m)
{
for (int i = 1; i <= m; i++)
for (int j = 1; j <= m; j++)
if (i == j)
c[i][j] = 1;
else
c[i][j] = 0;
day = 1;
for (int i = 0; i < n; i++)
cin >> G[i];
cin >> k;
for (int i = 0; i < k; i++)
{
cin >> a >> b;
c[a][b] = c[b][a] = 1;
}
for (int k = 1; k <= m; k++)
for (int i = 1; i <= m; i++)
for (int j = 1; j <= m; j++)
if (c[i][k]&&c[k][j])
c[i][j] = 1;
for (int i = 1; i < n; i++)
if (!c[G[i-1]][G[i]])
day++;
cout << day << endl;
cin >> n >> m;
}
// system("pause");
return 0;
}