题面
Fanvree 很聪明，解决难题时他总会把问题简单化。例如，他就整天喜欢把图转化为树。但是他不会缩环，那他怎么转化呢？ 这是一个有 n个点 m 条双向边的图，Fanvree 会选定一个节点，然后删掉这个节点和这个点连出去的边，如果变成了一棵树，那么这个节点便是可行的，什么是树呢？树也即无简单环的无向连通图。
告诉 Fanvree 可能的节点是什么。
对于 40%的数据：n，m<=1000；
另外存在 10%的数据：m=n-1；
另外存在 20%的数据：m=n；
对于 100%的数据：n，m<=100000
分析
这道水题告诉我，太自信会出事！出大事！
你看那40分的数据，枚举删哪个点dfs检验一下就过了，那10%的，说明不是个联通的图，找一下哪个点是单独的就过了。那20%，说明是树上加了个边，找一下就行了。这就70了！！
而我坚信自己写的是对的，缩了个点，然后删去一个点，剩下n-1个点，因此剩下n-2条边，需要删去m-(n-2)条边，只要找度数为这个就没错了吧？
然而我跑去缩点，缩了点再在那个环里找度数为m-(n-2)的边，完美错过正解。
其实根本不用缩点，只需要判一下割点，因为割点一定不在环内啊！！！！（显然，树上的每一个点都是割点）而环内可能有割点
哎。。。
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define N 100010
- #define RT register
- int n,m,t,cnt,tot,gro,cot,mark,root,child;
- int dfn[N],low[N],deg[N],cut[N],ans[N],first[N];
- struct email
- {
- int u,v;
- int nxt;
- }e[N*4];
- template<class T>
- inline void read(T &x)
- {
- x=0;int f=1;static char ch=getchar();
- while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
- while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
- x*=f;
- }
- inline void add(int u,int v)
- {
- e[++cnt].nxt=first[u];first[u]=cnt;
- e[cnt].u=u;e[cnt].v=v;
- }
-
- inline void tarjan(int u,int fa)
- {
- dfn[u]=low[u]=++tot;
- for(RT int i=first[u];i;i=e[i].nxt)
- {
- int v=e[i].v;
- if(v==fa)continue;
- if(!dfn[v])
- {
- tarjan(v,u);
- low[u]=min(low[u],low[v]);
- if(low[v]>=dfn[u]&&u!=root)
- cut[u]=1;
- if(u==root)child++;
- }
- else
- low[u]=min(low[u],dfn[v]);
- }
- if(child>1&&u==root)cut[u]=1;
- }
-
- int main()
- {
- read(n);read(m);
- for(RT int i=1;i<=m;i++)
- {
- int u,v;
- read(u),read(v);
- add(u,v);add(v,u);
- deg[u]++,deg[v]++;
- }
- for(int i=1;i<=n;i++)
- if(!deg[i])
- {root=i;break;}
- for(RT int i=1;i<=n;i++)
- if(!dfn[i])
- tarjan(i,i);
- for(RT int i=1;i<=n;i++)
- if(deg[i]==(m-(n-2))&&!cut[i])
- ans[++cot]=i;
- printf("%d\n",cot);
- for(RT int i=1;i<=cot;i++)printf("%d ",ans[i]);
- return 0;
- }
【NOIP模拟】种树
原文：https://www.cnblogs.com/NSD-email0820/p/9876108.html
