7-12 珍珠项链 (10 分)

7-12 珍珠项链 (10 分)

有n颗珍珠，编号为1至n，爸爸和小明做游戏，让小明把这些珍珠串成若干串项链。初始时n颗珍珠摆放在桌子上，每颗珍珠自成一个项链（即相当于有n个项链，每个项链只含一颗珍珠）。

每次爸爸让小明做如下 *** 作“a b”，表示将珍珠a所在的项链串在珍珠b所在的项链后面，形成一串新的项链，即a所在项链的第一个珍珠排在b所在项链的最后一个珍珠后面，如果珍珠a和b已在同一项链里，则忽略该 *** 作。

请编写程序，输出小明完成爸爸的所有 *** 作后，每个珍珠所在的项链的链头（该项链第一颗珍珠的编号）。

输入格式:
每个测试点包含多组测试数据，第一行1个整数 T ，表示测试数据组数。对于每组数据，第一行两个整数 n 和 m，分别表示珍珠个数和 *** 作次数。接下来 m 行，每行两个整数a和b，表示爸爸让小明执行的一个 *** 作。T≤5，1≤n, m≤30000，1≤a, b≤n。

输出格式:
输出为T 行，每行为 n个整数
a1 a2…an，每个整数后一个空格，ai
​(1≤i≤n)表示珍珠i所在项链的链头珍珠编号。

输入样例:
2
4 2
2 1
4 3
5 4
1 2
2 3
4 5
1 3

输出样例:
1 1 3 3
3 3 3 5 5
数据规模:
测试点0：1 ≤n, m ≤ 10；
测试点1：10 < n, m ≤100；
测试点2：100 < n, m ≤ 1000；
测试点3：1000 < n, m ≤10000；
测试点4：10000 < n, m ≤ 30000。

代码：

#include 
#include 
int t,n,m;
int a[200100];
void start(int n)///初始化
{
    for(int i=1;i<=n;i++)
        a[i]=i;
}
int find(int x)///找链头
{
    if(a[x]==x)
        return a[x];
    return a[x]=find(a[x]);
}
void print()
{
    for(int i=1;i<=n;i++)
            printf("%d ",find(i));
        printf("n");
}
int main()
{
    scanf("%d",&t);
    for(int i=0;i 
202201121353三
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5702484.html