無方向図の連通のサブ図を求めます--そしてセットを調べます
4110 ワード
タイトルの説明:
解題構想:主に思想を応用し、調査し、連通サブ図の個数を判断する.
2 S
10000 Kb
m+1 , n(1=30) m(1
解題構想:主に思想を応用し、調査し、連通サブ図の個数を判断する.
#include
#include
#include
using namespace std;
int root[100],rank[100];
// n
void init(int n){
for(int i=0;i0;
}
}
//
int find(int x){
if(root[x]==x){
return x;
} else{
return root[x]=find(root[x]);
}
}
// x y
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y)
return;
if(rank[x]else{
root[y]=x;
if(rank[x]==rank[y])
{
rank[x]++;
}
}
}
int main(){
int n,m,x,y;
cin>>n>>m;
init(n);
for(int i=0;i>x>>y;
unite(x,y);
}
int sum1[100]={0},sum2[100]={0};
int sum=0;
sum1[sum]=root[0];
sum++;
for(int i=1;ifor(int j=0;j<sum;j++)
{
if(root[i]==sum1[j])
break;
if(j==sum-1)
{
sum1[sum]=root[i];
sum++;
}
}
}
cout<<sum<for(int i=0;i<sum;i++){
for(int j=0;jif(root[j]==sum1[i]){
sum2[i]++;
}
}
}
sort(sum2,sum2+sum);
for(int i=0;i<sum;i++){
cout<" ";
}
return 0;
}