P8655 [蓝桥杯 2017 国 B] 发现环

FHenryh · 2023-05-06 21:49:51 · 题解

题目概述

题目传送门

在一棵树中新增一条边，使得这个图产生一个环，求在环上的点。

思路：

对于这道题我的思路类似于拓补排序。

首先可以将无向图转化为有向图，即将对于每条无向边变换为双向建边，就好处理了。

在这种情况下，很显然当一个点的入度大于或等于 2 时，即有不止一条边连向这个点时，该点就在环上。

我们可以建一个布尔类型 vis 数组来标记这个点的入度是否等于 1，那么这个点就不在环上，那么没有被标记的点就是我们要求的答案了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1; 
int n;
int in[N];
vector<int>e[N];
bool vis[N];//标记入度是否为1，即该点是否在环上
void topo()//拓补排序
{
    queue<int>q;
    for(int i=1;i<=n;i++)
        if(in[i]==1)//标记入度为1的点
        {
            q.push(i);
            vis[i]=true;
        }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<e[u].size();i++)
        {
            int v=e[u][i];
            in[v]--;
            if(in[v]==1)//标记入度为1的点
            {
                q.push(v);
                vis[v]=true;
            }
        }
    }
}
void print()//输出未标记的点
{
    for(int i=1;i<=n;i++)
        if(!vis[i])cout<<i<<' ';
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);//双向建边
        in[u]++;
        in[v]++;//两点的入度都增加
    }
    topo();
    print();
    return 0;
}