jquery网站开发教程,织梦网站提示保存目录数据时报,黄金多少钱一克,扬州市住房和城乡建设局网站问题描述 小明的实验室有N台电脑#xff0c;编号1~N。原本这N台电脑之间有N-1条数据链接相连#xff0c;恰好构成一个树形网络。在树形网络上#xff0c;任意两台电脑之间有唯一的路径相连。 不过在最近一次维护网络时#xff0c;管理员误操作使得某两台电脑之间增… 问题描述 小明的实验室有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 思路这道题打的标签似乎是并查集加DFS不过我的并查集思路可能有点问题有空再仔细想一下可以看下下面这个博客
http://t.csdnimg.cn/LSVct
我看了另一个网友的题解思路是用度来把叶子结点一个个剪掉最后会剩下一个环代码如下
#includebits/stdc.h
using namespace std;
const int N1e510;
int g[N];
vectorinta[N];
int main(){int n;cinn;int u,v;for(int i0;in;i){cinuv;g[u];g[v];a[u].push_back(v);a[v].push_back(u);//双向边}queueintq;//存叶子结点for(int i1;in;i){if(g[i]1)q.push(i);} while(!q.empty()){int uq.front();q.pop();for(int i0;ia[u].size();i){g[a[u][i]]--;if(g[a[u][i]]1)q.push(a[u][i]);}}for(int i1;in;i){if(g[i]1)couti ;}return 0;
}
