1.试题
问题描述
小明的实验室有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
2.算法分析
简化题目，即：求一个有n个节点和n条边的图中的环。易知，该环有且仅有1条。
通过画图、打草稿，可以看出：当将当前图中度为1的节点不断去除后，最终剩下的图形就是一个环，该环中的节点就是答案。这好比是剪树上的叶子，剪到最后只剩下枝干（环）了。
算法流程
将所有节点存入某个集合Node中，记录下每个节点i的度Deg[i]。在C++环境中建议使用set，插入和删除特定元素都很方便，且内部有序,方便输出。
预处理,将原图的度为1的节点加入一个队列q。
从q的队首取出一个节点x，将其从图中删除，包括Node和q中的x。注意更新与该节点相连的节点的各项参数。若有新的度为1的节点出现，将其加入队列。
重复步骤3，直到队列q为空。
将集合Node中的剩下元素全部输出。
时间复杂度
set类型单次插入和删除操作为$O(logN)$，平均对每个节点都要执行一次插入和删除操作。故时间复杂度为$O(NlogN)$。
3.代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<set>
#define MAXN 100005
#define MAXN2 200005
using namespace std;
int n,cnt=0;
int h[MAXN2]={0},Deg[MAXN]={0},In[MAXN]={0};
struct Edge{
int to,nxt;
}a[MAXN2];
set<int> Node;
queue<int> q;
inline void AddEdge(int x,int y)
{
cnt++; a[cnt].to=y; a[cnt].nxt=h[x]; h[x]=cnt;
}
int main()
{
int i,x,y;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>x>>y;
Deg[x]++;
Deg[y]++;
AddEdge(x,y);
AddEdge(y,x);
}
for(i=1;i<=n;i++)
{
if(Deg[i]==1) {q.push(i); In[i]=1;}
Node.insert(i);
}
while(!q.empty())
{
x=q.front();
q.pop();
Node.erase(x);
In[x]=0;
for(i=h[x];i;i=a[i].nxt)
{
y=a[i].to;
Deg[y]--;
if(Deg[y]==1&&!In[y]) {q.push(y); In[y]=1;}
}
}
set<int>::iterator it;
for(it=Node.begin();it!=Node.end();it++) cout<<*it<<" ";
return 0;
}
|
4.问题拓展（不一定想）
如何求一个图中的所有的环？