题目描述
小A参加了一个n人的活动，每个人都有一个唯一编号i(i>=0 & i<n)，其中m对相互认识，在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后，小A最多会认识多少人？
输入描述:
第一行聚会的人数：n（n>=3 & n<10000）； 第二行小A的编号: ai（ai >= 0 & ai < n)； 第三互相认识的数目: m（m>=1 & m < n(n-1)/2）； 第4到m+3行为互相认识的对，以','分割的编号。
输出描述:
输出小A最多会新认识的多少人？
示例1
输入
7 5 6 1,0 3,1 4,1 5,3 6,1 6,5
输出
3
一道非常常规的集合题，本人认为我这个aknow的设置还是很灵性的】
#include<iostream>
#include<memory.h>
using namespace std;
int root[10006];
void unionr(int a, int b){
root[a] = b;
}
int findroot( int v ){
if( root[v] == v ) return v;
else return root[v] = findroot(root[v]);
}
int main(){
int n,ai,m;
cin >> n >> ai >> m;
for( int i = 0 ; i < n ; i ++ ) root[i] = i;
int aknow = 0;
for( int i = 0 ; i < m ; i ++ ){
int a,b;
scanf("%d,%d",&a,&b);
if( a == ai || b == ai) aknow--;
unionr(findroot(a),findroot(b));
}
int aroot = findroot(ai);
for( int i = 0 ; i < n; i ++ )
if( findroot(i) == aroot && i != ai ) aknow++;
printf("%d",aknow);
return 0;
}
0 条评论