2017蓝桥杯C++ 发现环 - 并查集

淩亂°似流年 2022-03-07 00:34 188阅读 0赞

## 标题：发现环 ##

小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。  
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。  
为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？  
输入

第一行包含一个整数N。  
以下N行每行两个整数a和b，表示a和b之间有一条数据链接相连。  
对于30%的数据，1 <= N <= 1000  
对于100%的数据, 1 <= N <= 100000， 1 <= a, b <= N  
输入保证合法。

按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。

> 样例输入：  
> 5  
> 1 2  
> 3 1  
> 2 4  
> 2 5  
> 5 3  
> 样例输出：  
> 1 2 3 5

题解:  
一张草图, 聊表心意: 不知君能否会意.  
时间复杂度可以降为O(N), 当然必须还要加一张并查表. 下面的也不会太高.够过数据了 .

1, 2, 3表示第几个顶点.  
(1), (2)表示第几条边.  
环为 1, 2, 3, 4, 5.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70]

并查集解发现环，并且**输出环上的节点**。  
这里可以开两个并查集增加查找速度。先就这样就够了。

import java.util.Scanner;
    
    public class test { 
    	
    	static int N = 0;
    	static int num[] = new int[100000];// 存并查集表
    	
    	static int ans[] = new int[100000];// 存结果序列， 本题没有要求输出是哪几个节点，这里是我额外加的
    	static int count = 0;
    	
    	public static void main(String[] args) { 
    		Scanner in = new Scanner(System.in);
    		N = in.nextInt();
    		int a = 0;
    		int b = 0;
    		for(int i = 0; i < N; ++i){ 
    			a = in.nextInt();
    			b = in.nextInt();
    			// 录入并查集
    			if(num[a] == 0){ // 如果a没边 
    				if(num[b] != 0){ // 并且如果b有边， 那么a指向b 表示连边
    					num[a] = b;
    				}else{ // 否则a指向自己，b指向a 表示连边
    					num[a] = a;
    					num[b] = a;
    				}
    			}else{  // 如果a 有边
    				if(num[b] == 0){ // 如果b没边， 那么b指向a 表示连边
    					num[b] = a;
    				} else { // 如果b也右边， 那么有可能已经出现了环状
    					// 向前找 看是否能够找到相同的父亲
    					int ta = num[a];
    					int tb = num[b];
    					while(ta != num[ta]){ // 查表, 看是否成环
    						ta = num[ta];
    					}
    					while(tb != num[tb]){ // 查表, 看是否成环
    						tb = num[tb];
    					}
    					if(ta == tb){ // 如果出现环路
    						// 开始遍历环状的节点， 记录答案
    						int j = a;
    						ans[count++] = a;
    						ans[count++] = b;
    						while(j != num[j]){ // 查环上节点
    							j = num[j];
    							ans[count++] = j;
    						}
    						j = b;
    						while(j != num[j]){ // 查环上节点
    							j = num[j];
    							ans[count++] = j;
    						}
    						ans[--count] = 0;// 因为存在相同的顶级父节点，所以最后一个会重复
    						// 这里输入可能没有结束, 但是结果已经出来了, 所以, 可以直接输出结果了已经
    // break;
    					}else{ // 没有出现环路
    						num[b] = a;
    					}
    				}
    			}
    		}
    		// 输入结束
    		// 输出结果
    		System.out.println(count);
    		for(int i = 0; i < count; i++){ 
    			System.out.print(ans[i] + " ");
    		}
    		
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70]: /images/20220307/b619a52f7a3547be87c73ae30e683160.png