图的边
考虑有n个顶点的图(1<=n<=5000)，顶点命名为0,1,2，…，n-1；每个顶点都有一个数字ai (表示顶点i被标记为ai)，并且我们知道1<=ai<=100000 (1<=i<=n)。
顶点u和v是连通的当且仅当_
输入:在第一行n给出，在下n行a0，a1，a2，.，a(n-1)必须给出。
输出:图的边数。
我在下面写了一段正确的代码，但是我正在寻找一种更快的算法，它不检查每个顶点。
例如，如果时间限制为0.5秒，这不是一个好的算法。
#include<stdio.h>
int main(){
long long int a[5000],n,i,j,edge=0;
scanf("%lld",&n);
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
}
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(a[i]-a[j]==1 || a[i]-a[j]==-1){
edge=edge+1;
}
}
}
printf("%lld",edge);
}我有一个想法，我认为它可以帮助进步更快，但我不知道如何写代码:我想，如果我们能计算出，对于一个恒数k，多少个ai‘等于k，然后把它们放在另一个数组中，它可以使检查的进程更快，例如，如果n=12和ai’s是1，2，4，5，4，5，7，7，7，7，7，7，这里有一个1，1，2，2，4‘s，3 5’s，1，6和4，7，所以这些相等的ai‘s不需要与其他值一起检查超过一次。
回答 2
Stack Overflow用户
发布于 2018-11-10 17:23:42
我终于找到了一个很好的algorithm.Thanks来帮你。这是我的密码：
#include<stdio.h>
int main(){
long long int a[100000],b[100002]={0},n,i,j,edge=0;
scanf("%lld",&n);
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
b[a[i]]++;
}
for(i=1;i<100002;i++){
edge=edge+b[i]*b[i-1];
}
printf("%lld",edge);
}Stack Overflow用户
发布于 2018-11-09 17:02:22
如果OP的代码确实是正确的，那么顶点标签k并不是唯一的，而且许多不同的顶点可以有相同的标签。
假设您的数组n为100,002个无符号整数，编号为0到100,001，每个数组都能够表示0到5,000之间的值。将它们初始化为零。
添加标记为k的顶点时，增量无符号整数nk。如果nk-1 + nk+1是非零的，那么添加这个顶点就会产生许多新的边.
如果计算创建的边数，则在添加最后一个顶点后立即得到结果。
如果顶点标签是唯一的，但可能有(错误地)重复标签k被忽略，那么：
假设您有一个由100,002个标志组成的数组，编号从0到100,001 (包括在内)，并初始化为all空。
每当您看到标记为k的顶点时，请检查标志k是否已经设置。如果是，则这是一个要忽略的重复标志。
否则，设置标志，并检查标志k-1和k+1。如果设置了其中一个标志，则创建一个新边缘；如果设置了两个标志，则创建两个新边缘。如果两者都是清晰的，则没有创建新的边缘。
如果计算创建的边数，则在添加最后一个顶点后立即得到结果。
https://stackoverflow.com/questions/53228093
复制相似问题
腾讯云开发者
