社区讨论
萌新刚学tarjan,请求大佬帮助!!!
P3388【模板】割点(割顶)参与者 5已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @mi7w4eiq
- 此快照首次捕获于
- 2025/11/21 04:35 4 个月前
- 此快照最后确认于
- 2025/11/21 06:32 4 个月前
样例未过!!!
CPP#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define MAXN 20100
#define MAXM 101000
struct node
{
int u,v,next;
}edge[MAXM];
int n,m,x,y,ans,index,cnt;
int head[MAXN],LOW[MAXN],DFN[MAXN],a[MAXN];
void add_edge(int u,int v)
{
edge[++cnt].next=head[u];
edge[cnt].u=u;
edge[cnt].v=v;
head[u]=cnt;
}
void tarjan(int x,int rt)
{
//printf("%d %d\n",x,rt);
int tot=0;
LOW[x]=DFN[x]=++index;
for (int i = head[x] ; i ; i = edge[i].next)
{
int v=edge[i].v;
if(!DFN[v])
{
tarjan(v,rt);
LOW[x]=min(LOW[x],LOW[v]);
if(x!=rt&&DFN[x]<=LOW[v]) a[i]=1;
if(x==rt) ++tot;
}
LOW[x]=min(LOW[x],DFN[v]);
}
if(tot>=2&&x==rt) a[rt]=1;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i = 1 ; i <= m ; ++ i)
{
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
for (int i = 1 ; i <= n ; ++ i)
{
if(!DFN[i]) tarjan(i,i);
}
for (int i = 1 ; i <= n ; ++ i)
{
if(a[i]) ++ans;
}
printf("%d\n",ans);
for (int i = 1 ; i <= n ; ++ i)
{
if(a[i]) printf("%d ",i);
}
return 0;
}
回复
共 15 条回复,欢迎继续交流。
正在加载回复...