【UOJ#67】新年的毒瘤 Tarjan 割点

#67. 新年的毒瘤

UOJ直接黏贴会炸...    还是戳这里吧: http://uoj.ac/problem/67#tab-statement

Solution

看到这题的标签就进来看了一眼。

想了一个比较胡搞的方法,因为删除割点就会产生多个块,那么割点是不能被割的,所以只能割非割点。

删除非割点后是棵树,说明边数是N-2...然后求一下每个点的度...

只要不是割点,并且割掉这个点剩的边是N-2条,就输出.....

然后就A了...感觉还是很科学的。 (这个Tarjan模板太好打了...顺便求了个点双...)

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define LL long long
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 100010
int N,M,tot;
LL sum;
struct EdgeNode{int next,to,from;}edge[MAXN<<];
int head[MAXN],cnt=;
void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
#define Pa pair<int,int>
vector<int>BCC[MAXN];
Pa st[MAXN]; int top;
int dfn[MAXN],low[MAXN],dfsn,cut[MAXN],bcc,belong[MAXN],d[MAXN];
void Tarjan(int now,int last)
{
dfn[now]=low[now]=++dfsn; int son=;
for (int i=head[now]; i; i=edge[i].next)
if (!dfn[edge[i].to])
{
st[++top]=make_pair(now,edge[i].to); son++;
Tarjan(edge[i].to,now); low[now]=min(low[now],low[edge[i].to]);
if (dfn[now]<=low[edge[i].to])
{
cut[now]=; bcc++; BCC[bcc].clear(); int tnow=-,tto=-;
while ()
{
tnow=st[top].first,tto=st[top].second; top--;
if (belong[tnow]!=bcc) BCC[bcc].push_back(tnow),belong[tnow]=bcc;
if (belong[tto]!=bcc) BCC[bcc].push_back(tto),belong[tto]=bcc;
if (tnow==now && tto==edge[i].to) break;
}
}
}
else if (dfn[edge[i].to]<dfn[now] && edge[i].to!=last)
st[++top]=make_pair(now,edge[i].to),low[now]=min(low[now],dfn[edge[i].to]);
if (last< && son==) cut[now]=;
}
int main()
{
N=read(),M=read();
for (int x,y,i=; i<=M; i++) x=read(),y=read(),InsertEdge(x,y),d[x]++,d[y]++;
for (int i=; i<=N; i++) if (!dfn[i]) Tarjan(i,-);
for (int i=; i<=N; i++) if (!cut[i] && d[i]==M-N+) tot++;
printf("%d\n",tot);
for (int i=; i<=N; i++) if (!cut[i] && d[i]==M-N+) printf("%d ",i); puts("");
return ;
}
上一篇:Oracle 11.2.4.0 ACTIVE DATAGUARD 单实例安装(COPY创建备库)


下一篇:Java for LeetCode 081 Search in Rotated Sorted Array II