发现环

问题描述
　　小明的实验室有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

解题思路

递归删除度为1的节点即可

代码、

#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<iomanip>
#include<map>
#define N 1000000+10 
using namespace std;
vector<int> v[N];
int n;
int num[N] ;
//看看是否存在度为1的节点 
bool find1()
{
	for(int i = 1;i <= n;i++)
	{
		if(num[i]==1)
		return true;
	}
	return false;
}
int main()
{
    freopen("in.txt","r",stdin);
    //数据输入
	cin >> n;
	for(int i = 0;i < n;i++) 
	{
		int a,b;
		cin >> a >>b;
		//m[a] = b;
	//	m[b] = a;
		v[a].push_back(b);
		v[b].push_back(a);	
		num[a]++;
		num[b]++;
	}
	//删除所有度为1 的节点 
	while(find1()){
		for(int i = 1;i <= n;i++)
		{
			if(num[i]==1){
				num[i]--;
				num[v[i][0]]--;
			}
		}
	}
	//输出 
	bool flag = true;
	for(int i = 1;i <= n;i++)
	{
		if(num[i]==2){
			if(flag){
				cout << i ;
				flag = false; 
			}
			else{
				cout << " " << i ;
			}
		}
	
	}
}

别人同BFS做的

#include <cstdio>
#include <queue>
#include <vector>
#define MAX 100010
using namespace std;
 
vector<int> MGraph[MAX];
int degree[MAX];
int visit[MAX];
 
void topSort( int n ) {
    queue<int> q;
    for( int i = 1; i <= n; i++ ) {
        if( degree[i] == 1 ) {
            q.push( i );
            visit[i] = 1;
        }
    }
    while( !q.empty() ) {
        int cur = q.front();
        q.pop();
        for( int i = 0; i < MGraph[cur].size(); i++ ) {
            int v = MGraph[cur][i];
            degree[v]--;
            if( degree[v] == 1 ) {
                visit[v] = 1;
                q.push( v );
            }
        }
    }
}
int main() {
    int n;
    scanf( "%d", &n );
 
    for( int i = 0; i < n; i++ ) {
        int a, b;
        scanf( "%d%d", &a, &b );
        MGraph[a].push_back( b );
        MGraph[b].push_back( a );
        degree[a]++; degree[b]++;
    }
 
    topSort( n );
    bool flag = true;
    for( int i = 1; i <= n; i++ ) {
        // 把没有入队的元素打印出来，注意行末不能有空格
        if( visit[i] == 0 ) {
            if( flag ) { printf( "%d", i ); flag = false; }
            else printf( " %d", i );
        }
    }
    return 0;
}