编程题

1735:环上计数


时间限制: 1000 ms         内存限制: 32768 KB
提交数:189    通过数: 22

【题目描述】

给定一张$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$。

查看答案
赣ICP备20007335号-2