最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 环上计数

C++ 少儿编程 1267浏览 0评论

友情提示:380元/半年,儿童学编程,就上码丁实验室

【题目描述】

给定一张$n$个点,$m$条边的无向图。求出有多少条边不在任何一个简单环上和有多少条边在至少两个简单环上。保证图中没有重边和自环,不保证原图连通。

【输入】

输入包含多组数据。

对于每组数据:

第一行包含两个整数$n$和$m$,表示无向图的点数和边数。

接下来的$m$行,每行包含两个整数$u,v$,表示无向图的一条边,点从$0$开始编号。

当$n=0$且$m=0$时输入结束。

【输出】

对于每组数据输出一行,包含两个整数,分别表示有多少条边不在任何一个简单环上和有多少条边在至少两个简单环上。

【输入样例】

8 10
0 1 
1 2 
2 3 
3 0 
3 4 
4 5 
5 6 
6 7 
7 4 
5 7 
0 0

【输出样例】

1 5

【提示】

【数据规模】

对于100%的数据,$1≤n≤10000,1≤m≤100000$。

您必须 登录 才能发表评论!