冗余连接

题目描述

有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图），如图：

现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图：

先请你找出冗余边，删除后，使该图可以重新变成一棵树。

输入描述

第一行包含一个整数 N，表示图的节点个数和边的个数。

后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

输出描述

输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

输入示例

3
1 2
2 3
1 3

输出示例

1 3

提示信息

图中的 1 2，2 3，1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边，所以输出结果为 1 3

数据范围：

1 <= N <= 1000.

思路：这道题比较简单，因为是无向图，所以在并查集的基础上使用isSame函数进行判断即可。

#include<iostream>
#include<vector>
using namespace std;

int n;
vector<int> parent(1001, 0);

//初始化并查集的各结点的根
void init(){
    for(int i = 0; i < n; i ++){
        parent[i] = i;
    }
}

//找结点的根
int find(int u){
    return u == parent[u] ? u : parent[u] = find(parent[u]);//路径压缩
}

//比较两结点的根是否相同
bool isSame(int u, int v){
    u = find(u);
    v = find(v);
    return u == v;
}

//将两结点加入并查集
//存在v->u这样一条边
void join(int u, int v){
    u = find(u);
    v = find(v);
    if(u == v) return;
    parent[v] = u;
}

int main(){
    while(cin >> n){
        init();
        int node1, node2;
        for(int i = 0; i < n; i ++){
            cin >> node1 >> node2;
            if(isSame(node1, node2)){
                cout << node1 << " " << node2 << endl;
                return 0;
            }
            join(node1, node2);
        }
    }
}