#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int mxn=1e6+5; int s[mxn], n, m, a[mxn], sum=0, v[mxn]; int check(int x) { if(x!=s[x]) return check(s[x]); return s[x]; } int main() { scanf("%d", &n); memset(v,0,sizeof v); for(int i=1;i<=n;i++) s[i]=i;//初始化 for(int i=1;i<=n;i++){ scanf("%d", &m); if(m==-1){ sum++; v[i]=1; //标记父结点 a[i]++; } else s[i]=check(m); } printf("%d\n", sum); for(int i=1;i<=n;i++){ if(i!=s[i]){//不属于父结点 s[i]=check(s[i]); a[s[i]]++; } } for(int i=1;i<=n;i++){ if(v[i]) printf("%d %d\n", i, a[i]); } return 0; } 中三个数组的作用是什么
时间: 2024-04-19 14:28:45 浏览: 8
这段代码中的三个数组的作用如下:
1. `s[mxn]` 数组:用于存储每个节点的父节点,用于实现并查集(Union-Find)的功能。在初始化时,每个节点的父节点都是自己。
2. `a[mxn]` 数组:用于记录每个父节点下的子节点数量。对于每个节点,如果其父节点为-1,则将其标记为父节点,并将其对应的 `a` 值加1。
3. `v[mxn]` 数组:用于标记父节点。当输入的节点值为-1时,表示此节点为父节点,将其对应的 `v` 值设置为1,方便后续输出。
总结起来,`s` 数组实现了并查集的功能,`a` 数组记录了每个父节点的子节点数量,`v` 数组标记了父节点。
相关问题
#include <iostream> #include<algorithm> #include<cmath> #include <queue> using namespace std;
#include <iostream>:这是C++标准库中的头文件,用于输入输出流操作,包括cin、cout等。
#include<algorithm>:这是C++标准库中的头文件,用于提供各种算法操作,如排序、查找等。
#include<cmath>:这是C++标准库中的头文件,用于提供数学函数操作,如绝对值、平方根等。
#include <queue>:这是C++标准库中的头文件,用于提供队列操作,包括入队、出队等。
using namespace std;:这是C++的命名空间声明,表示使用std命名空间,可以直接使用std中的函数和对象。
#include<iostream> #include<cstdio> using namespace std;是什么意思
#include<iostream> #include<cstdio> using namespace std; 是C++中的预处理指令,用于引入头文件和命名空间。
1. #include<iostream> 是引入iostream头文件,其中包含了输入输出流的定义,例如cout和cin等。
2. #include<cstdio> 是引入cstdio头文件,其中包含了C语言标准输入输出函数的定义,例如printf和scanf等。
3. using namespace std; 是使用std命名空间,std是C++标准库的命名空间,其中包含了很多常用的函数和类。
这些预处理指令的作用是为了在程序中能够使用输入输出流和标准库函数,使得程序更加方便和简洁。