复读机

题目链接：复读机
题目描述：

在某华大学里有一个无聊的群组，群内的所有成员都是复读机，他们疯狂复读着别人的消息。然而复读机们在群内也是有阵营的，一个阵营的复读机会根据心情选择是否复读同一个阵营的成员的消息，但绝对不会去复读其他阵营的消息。

群内有n个人（标号1-n号）。现在群内聊天记录中一共有m条消息。请根据这些消息，判断出如果群内第i号成员（1<=i<=n）发一条十分有趣的消息，在同一阵营的成员都会去复读这条消息情况下，那么这条消息会被复读几次？

如果无法判断i号成员和j号成员是否为同一阵营，则视为不同阵营。

输入描述:
输入包括m+1行。第一行包括两个整数n,m；其后的m行为当前的聊天记录，每行包括一个数字i和一个字符串s（表示i发了一条消息）。（保证1<=i<=n，m<=100000，消息的字符串总长不超过100000）
输出描述:
输出一行，包括n个数字。第i个数字表示第i号成员的有趣消息会被复读几次（1<=i<=n）。数字与数字之间用一个空格分隔。
示例1
输入
复制
3 5
1 a
2 a
1 b
2 c
3 c
输出
复制
2 2 2
说明
对于样例1： 由聊天记录的前两行可以得出2号和1号为同一阵营，由最后两行可得3号和2号为同一阵营，所以三者为同一阵营，他们三个发送的消息会被复读2次，故输出为2 2 2；
示例2
输入
复制
3 3
1 a
2 b
3 c
输出
复制
0 0 0
说明
对于样例2：1，2，3号无法判断是否为同一阵营，视为不同阵营。
备注:
对于复读的概念：

若聊天记录为

1 a

2 a

3 a

属于2，3号复读了1号的消息。

若聊天记录为

1 a

2 b

3 a

不构成任何复读，1的‘a‘和3的‘a’均属于自己原创消息。

题意分析：
具体并查集的思想我也解释不清，可以参考这篇博客：
https://boctorio.com/2019/03/02/%E5%B9%B6%E6%9F%A5%E9%9B%86/
这道题就是当你检测到相邻的两次输入的字符串是相等的就需要把这两个字符串的所对应的前面的数字看成是一组的。最后输出的时候，就输出和它同组的数目减一就行了（因为要除去它自己）。
解题思路还是很简单的，实现起来的话用并查集就行了。

代码实现

#include<iostream>
using namespace std;
const int maxn=100010;
struct name
{
    int num;
    string sym;
}a[maxn];
int pre[maxn];
int sum[maxn];
void init(int n)
{
    for(int i=1;i<=n;i++)
        pre[i]=i;
}
int find(int x)
{
    return pre[x]!=x?pre[x]=find(pre[x]):x;
}
void Union(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x<y)
        pre[y]=x;
    else
        pre[x]=y;
}
int main()
{
    int n,m;
    cin>>n>>m;
    init(n);
    cin>>a[0].num>>a[0].sym;
    for(int i=1;i<m;i++)
    {
        cin>>a[i].num>>a[i].sym;
        if(a[i].sym==a[i-1].sym)
            Union(a[i].num,a[i-1].num);
    }
    for(int i=1;i<=n;i++)
    {
        find(i);
        sum[pre[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(i!=1)
            cout<<" ";
        cout<<sum[pre[i]]-1;
    }
    cout<<endl;
    return 0;
}