首页 > 代码库 > qscoj

qscoj

#include<bits/stdc++.h>
#define MAXN 1005
using namespace std;
int book[MAXN][MAXN];
int dalao[MAXN];
int n;
string a;
void mem()
{
    for(int i=1;i<=n;i++)
    {
        dalao[i]=i;
    }
    memset(book,0,sizeof(book));
}
int getboss(int v)
{
    if(dalao[v]==v) return v;
    else {
        dalao[v]=getboss(dalao[v]);
        return dalao[v];
    } 
}
void hebin(int v,int u)
{
    int t1,t2;
    t1=getboss(v);
    t2=getboss(u);
    if(t1!=t2)
    {
        dalao[t2]=dalao[t1];
    }
}
int main()
{
    while(cin>>n)
    {
        mem();
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a;
            for(int j=0;j<a.size();j++)
            {
                book[i][a[j]]++;
            }
        }
        for(int i=1;i<=n-1;i++)
        {
            int flag=1;
            for(int j=i+1;j<=n;j++)
            {
                
                for(int k=A;k<=Z;k++)
                {
                    if(book[i][k]!=book[j][k]) {
                    flag=0;break;}
                }
                if(flag==1)
                {
                    hebin(i,j);
                } 
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(dalao[i]==i) ans++;
        
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

qscoj