题意:判断是否成环,成环则error++
使用并查集进行判断即可,另外,题目要求的输入判断也是一个注意点
#include<iostream>
using namespace std;
const int maxn = 100005;
int pre[maxn];
int find(int x){
return pre[x] == x?x:pre[x] = find(pre[x]);
}
int main(){
int a,b;
while(scanf("%d", &a) == 1){
for(int i = 0; i <= maxn; i++) pre[i] = i;
int error = 0;
while(a!=-1){
scanf("%d", &b);
a = find(a);
b = find(b);
if(a==b){
error++;
}else{
pre[a] = b;
}
scanf("%d", &a);
}
printf("%d\n", error);
}
return 0;
}
网友评论