kskkk

用户名：liuxin123

访问量：1824

签　名：

等　　级
排　　名	6357
经　　验	1426
参赛次数	0
文章发表	5
年　　龄	0
在职情况	学生
学　　校	qlu
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-日期问题-题解(C++代码)
浏览：324

你可能喜欢

蓝桥杯2017年第八届真题-发现环-题解(C语言代码)--无向图的拓扑排序

　　作者: kskkk　　　　发表时间：2020-02-09 02:17:22 浏览：410　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-发现环

无向图的拓扑排序，不过也学习了别人写的并查集+搜索的方法、、、

和有向图不同的是：不断删除入度为1的顶点，具体就是用一个vis[]数组标记一下，而且这样也避免了无向图边的重复访问！！！（判断一个点重复访问不可以用入度数组in[]==1来判断，犯错点）

```cpp
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

const int N = 1e5+5;
vector<int> g[N], ans;
queue<int> q;
int n, in[N];
bool used[N]={false};

void tuopu()
{
    for(int i = 1; i <= n; i++)
        if(in[i]==1)
            used[i]=true,   q.push(i);
    while(!q.empty())
    {
        int x = q.front();  q.pop();
        for(int i = 0; i < g[x].size(); i++)
        {
            if(used[i])
                continue;
            int nx = g[x][i];
            in[nx]--;
            if(in[nx]==1)
                used[nx]=true,  q.push(nx);
        }
    }
}
int main()
{
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        int a, b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
        in[a]++;    in[b]++;
    }
    tuopu();
    for(int i = 1; i <= n; i++)
        if(!used[i])
            ans.push_back(i);
    sort(ans.begin(), ans.end(), less<int>());
    cout<<ans[0];
    for(int i = 1; i < ans.size(); i++)
        cout<<' '<<ans[i];
    return 0;
}

```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

kskkk

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C二级辅导-公约公倍（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

蓝桥杯2017年第八届真题-发现环-题解(C语言代码)--无向图的拓扑排序

评论区

精彩推荐

【回文数(二)】（C++代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

DNA （C语言描述，数据结构）

三角形（C++代码）递推

三角形（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

字符逆序（C语言代码）

kskkk

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

蓝桥杯2017年第八届真题-发现环-题解(C语言代码)--无向图的拓扑排序

评论区

精彩推荐

【回文数(二)】 （C++代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

DNA （C语言描述，数据结构）

三角形 （C++代码）递推

三角形 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

字符逆序 （C语言代码）

C二级辅导-公约公倍（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

　　评论区

【回文数(二)】（C++代码）

三角形（C++代码）递推

三角形（C语言代码）

字符逆序（C语言代码）