SDNU 1533 寻找复读机

Description

某小队里一共有 n 个人，他们的编号是 1..n，其中有一些人本质上是复读机。

底层群员柳予欣发现，如果一个人的本质是复读机，那么他每次发的消息一定跟群里的上一条消息一样，特别地第一个发消息的人一定不是复读机。

某不愿透露姓名的管理员现在搞到了一份聊天记录，他想请你找出所有可能是复读机的群友。

Input

多组输入。

每组输入的第一行两个正整数 n,m，表示群里的人数和聊天记录的总条数。

接下来 m 行按时间顺序给出聊天记录，每行有一个正整数 x 和一个小写字母字符串 S，表示群友 x 发了消息 S。

1≤ n≤ 1000

1≤ m≤ 1000

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#define ll long long

int main()
{
    char str[1010][110];
    int ans[1010], a, x, n, m, j, temp;
    while (~scanf("%d%d", &n, &m))
    {
        temp = 0;//控制空格输出
        memset(ans, 0, sizeof(ans));//设每个人都是复读机
        scanf("%d%s", &a, str[0]);
        for (int i = 1; i < m; i++)
        {
            scanf("%d%s", &x, str[i]);//第x个人的复读情况
            if (strcmp(str[i], str[i - 1]))    ans[x] = 1;//若不是复读机，则单独标记
        }
        ans[a] = 1;//特别的，第一个肯定不是复读机
        for (int i = 1; i <= n; i++)
            if (!ans[i])//如果是复读机
            {
                if (temp)//控制空格
                    printf(" ");
                temp = 1;
                printf("%d", i);
            }
        printf("\n");
    }
    return 0;
}

 

1≤ |S|≤ 100

Output

输出一行，将所有可能是复读机的群友的编号按照从小到大排序后输出，每两个编号之间隔一个空格。

Sample Input

3 5
1 gugugu
2 gugugu
1 gugu
3 tingzhifudu
2 tingzhifudu

Sample Output

2