18733 排队

妖狐艹你老母 2023-02-13 12:23 11阅读 0赞

时间限制:1000MS 代码长度限制:10KB  
提交次数:0 通过次数:0

题型: 编程题 语言: 不限定  
Description  
操场上有好多好多同学在玩耍，体育老师冲了过来，要求他们排队。同学们纪律实在太散漫了，老师不得不来手动整队：  
“A，你站在B的后面。”  
“C，你站在D的后面。”  
“B，你站在D的后面。哦，去D队伍的最后面。”

更形式化地，初始时刻，操场上有 n 位同学，自成一列。每次操作，老师的指令是 “x y”，表示 x 所在的队列排到 y 所在的队列的后面，  
即 x 的队首排在 y 的队尾的后面。（如果 x 与 y 已经在同一队列，请忽略该指令） 最终的队列数量远远小于 n，老师很满意。  
请你输出最终时刻每位同学所在队列的队首（排头），老师想记录每位同学的排头，方便找人。

输入格式  
第一行两个整数 n 和 m (n,m≤30000)，紧跟着 m 行每行两个整数  
x 和 y (1≤x,y≤n)。

输出格式  
仅一行 n 个整数，表示每位同学所在队列排头同学的编号。

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

输出样例  
3 3 3 5 5

提示  
题目来源于http://openjudge.cn/  
某大学数据结构与算法期末考试的第一题

解题思路：使用并查集，祖先不同的并祖先即可，如果自己没有祖先的话，那么视自己为自己的祖先。另外要每次查的时候可以进行路径压缩，这样在下次查找的时候可以提高效率，可以避免某些特殊情况超时。

#include<iostream>
    using namespace std;
    int pre[30005];
    int find(int x)
    { 
    // int cur=pre[x];//往上查 
    // while(cur!=x)
    // { 
    // x=cur;
    // cur=pre[cur];
    // }
    // return cur;//找到源头了//此写法缺少路径压缩 
        if(x==pre[x])
        return x;
        return pre[x]=find(pre[x]); 
    }
    void  merge(int x,int y)//将y并到x
    { 
    	int s1=find(x);
    	int s2=find(y);
    	if(s1!=s2)
    	pre[s2]=s1;//y的上面是x 
     } 
     int main()
     { 
     	int n,m,i,x,y;
     	cin>>n>>m;
     	for(i=1;i<=n;i++)
     	pre[i]=i;
     	for(i=1;i<=m;i++)
     	{ 
     		cin>>x>>y;
     		merge(y,x);
    	 }
    	 for(i=1;i<=n;i++)
    	 cout<<find(i)<<" ";
    	 return 0;
     }