一、相关概念

二、题目

题目

输入：标题：发现环
小明的实验室有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

思路

此处用邻接表存储图

用输入的
5
1 2
3 1
2 4
2 5
5 3
构建图

代码

public class 发现环 {
    public static void main(String[] args) {
        new 发现环().exe();
    }

    public void exe() {
        Scanner scan=new Scanner(System.in);
        int N=scan.nextInt();
        ArcGraph g=new ArcGraph(N,N);
        for(int i=0;i<N;i++){
            int vi=scan.nextInt();
            int vj=scan.nextInt();
            g.insertAdj(vi,vj);
            g.insertAdj(vj,vi);
        }
        DFS(g,1,new int[g.n+1]);
    }
    
    /**
     * 图的深度优先遍历
     * 尽可能深地搜索一棵树
     * 从节点v开始访问->访问与v邻接 & 未被访问的节点w1,—>访问与w1邻接 & 未被访问的节点
     * ->......->直到访问到wx(其所有邻接节点都被访问过了)，
     * ->回退到上一访问节点，重复上述过程，直到回退完毕
     * 【这是带回退的递归过程】
     * 特点：1，需要一个int[] visited作为节点访问标记
     * @param g
     * @param v
     */
    public void DFS(ArcGraph g,int v,int[] visited){
        visited[v]=1;
        visit(g,v);
        ArcNode p=g.nodes[v].firstArc;
        while(p!=null){
            if(visited[p.num]==0){
                DFS(g,p.num,visited);
            }
            p=p.nextNode;
        }
    }
    private void visit(ArcGraph g,int v) {
//      System.out.println(g.nodes[v].info);
        System.out.println(v);
    }
}

/**
 * 
* <p>Description: 
* 邻接表
* </p>  
* @author 杨丽金  
* @date 2018-4-23  
* @version 1.0
 */
public class ArcGraph {
    class ArcNode{
        // 节点编号（从1开始）
        int num;
        // 下一个邻接点
        ArcNode nextNode;
        public ArcNode(int num){
            this.num=num;
            nextNode=null;
        }
    }
    class VNode{
        // 编号（从1开始）
        int num;
        // 顶点信息
        String info;
        // 第一个边的邻接点
        ArcNode firstArc;
        public VNode(int num){
            this.num=num;
            this.info=null;
            firstArc=null;
        }
    }
    // 顶点个数
    int n;
    // 边个数
    int e;
    // 顶点
    VNode[] nodes;
    
    public ArcGraph(int n,String[] data){
        this.n=n;
        nodes=new VNode[n+1];
    }
    
    public ArcGraph(int n,int e){
        this.n=n;
        this.e=e;
        nodes=new VNode[n+1];
        for(int i=1;i<=n;i++){
            nodes[i]=new VNode(i);
        }
    }

    /**
     * 为节点vi添加邻接节点vj
     * @param vi
     * @param vj
     */
    public void insertAdj(int vi, int vj) {
        ArcNode p=nodes[vi].firstArc;
        if(p==null){
            nodes[vi].firstArc=new ArcNode(vj);
        }else{
            while(p.nextNode!=null){
                p=p.nextNode;
            }
            p.nextNode=new ArcNode(vj);
        }
        
    }
}

测试

输入的图.png

结果输出.png