题解

1 条题解

  • 0
    @ 2022-09-25 21:58:54
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,ans;
    int fa[2005];
    int find(int x)
    {
        if(fa[x]!=x)
            fa[x]=find(fa[x]);
        return fa[x];
    }
    void merge(int x,int y)
    {
        int xx=find(x),yy=find(y);
        if(xx==yy)
            return;
        if(xx<=n)
            fa[yy]=xx;
        else
            fa[xx]=yy;
    }
    inline int read()
    {
        int x=0,f=1;
        char c=getchar();
        while(c>'9'||c<'0')
        {
            if(c=='-')
                f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            x=x*10+c-'0';
            c=getchar();
        }
        return x*f;
    }
    int main()
    {
        n=read(),m=read();
        for(int i=1; i<=2*n; i++)
            fa[i]=i;
        for(int i=1; i<=m; i++)
        {
            char c;
            cin>>c;
            int x,y;
            x=read(),y=read();
            if(c=='F')
                merge(x,y);
            else
            {
                merge(x,y+n);
                merge(x+n,y);
            }
        }
        for(int i=1; i<=n; i++)
            if(fa[i]==i)
                ans++;
        cout<<ans<<endl;
        return 0;
    }
    
  • 1

信息

ID
1723
难度
7
分类
并查集数据结构 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者