NC219735. 传统的延续
描述
在一个神秘的古老国度有着这样的一个传统，如果一个城市曾向另一个城市宣誓，那么这个城市的最高建筑不得高于效忠的城市，一个城市最多只会宣誓一次。
特别的如果城市A曾向B宣誓，B城市曾向C城市宣誓，那么我们会认为城市A也会向城市C效忠。
由于国家的快速发展，不断有新的城市出现，也就不断有新的效忠关系出现，关系实在是错综复杂。
所以现在请你写一个程序来判断有多少个城市对之间的关系任然是合法的。
一对城市的关系被看作是合法的当且仅当城市之间存在效忠关系，且附属城市的最高建筑不高于效忠城市的最高建筑。
输入描述
第1行，包含两个正数n, m(2 <= n <= 105, 0 <= m <= n-1) 表示城市的数量和效忠关系。第2 ~ 1 + m 行，包含两个整数 u, v, (1 <= ui,vi <= n) 表示vi 曾向 ui 宣誓。不存在不合法的宣誓关系。第2 + m 行，包含 n 个整数 heighti (1 <= heighti <= 105) 表示第 i 个城市现在的最高建筑高度。
输出描述
一行，一个整数表示合法的城市关系对数。
示例1
输入:
5 4 1 2 1 3 2 4 3 5 10 12 11 10 12
输出:
2
说明:
示例2
输入:
5 3 1 2 1 3 4 5 10 12 11 12 12
输出:
1
说明:
C 解法, 执行用时: 15ms, 内存消耗: 1460K, 提交时间: 2022-12-06 16:23:39
#include<stdio.h>
int main (){
int n=0,m=0,i=1,sum=0,j=1,u=0,v=0,t=0;
int c[100001]={0},h[100001]={0};
scanf("%d %d",&n,&m);
for(;i<=m;i++){
scanf("%d %d",&u,&v);
c[v]=u;
}
for(i=1;i<=n;i++){
scanf("%d",&h[i]);
}
for(i=1;i<=n;i++){
t=c[i];
while(t){
if(h[i]<=h[t]) sum++;
t=c[t];
}
}
printf("%d",sum);
return 0;
}
C++(clang++11) 解法, 执行用时: 32ms, 内存消耗: 656K, 提交时间: 2021-03-21 22:46:18
#include<iostream>
using namespace std;
int k,f[100005],heigh[100005],n,m,ans,a,b;
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
f[b]=a;
}
for(int i=1;i<=n;i++)
{
cin>>heigh[i];
}
for(int i=1;i<=n;i++)
{
int k=i;
while(k)
{
if(heigh[i]<=heigh[f[k]])
{
ans++;
}
k=f[k];
}
}
cout<<ans<<endl;
return 0;
}