社区讨论
萌新,啥都不会,求助
P3388【模板】割点(割顶)参与者 7已保存回复 19
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 19 条
- 当前快照
- 1 份
- 快照标识符
- @mi85x18h
- 此快照首次捕获于
- 2025/11/21 09:09 4 个月前
- 此快照最后确认于
- 2025/11/21 09:46 4 个月前
RT,WA爆0,样例测过,自造垃圾数据测过,有的多了有的少了有的求错了,求助
CPP#include <iostream>
#include <cstdio>
#define yycoi 0
const int N=20000;
const int M=100000;
inline int mymin(int x, int y)
{
return x<y?x:y;
}
inline int mymax(int x, int y)
{
return x>y?x:y;
}
int n, m;
struct cfs
{
int to, nxt;
} edge[2*M+20];
int head[N+10];
inline void add_edge(int f, int t)
{
++head[0];
edge[head[0]].to=t;
edge[head[0]].nxt=head[f];
head[f]=head[0];
return;
}
int fa[N+10];
// book[i] == i deleted?
bool book[N+10], vis[N+10];
int dfn[N+10], low[N+10];
int ans;
void tarjan(int i)
{
int child=0;
vis[i]=1;
++dfn[0];
dfn[i]=dfn[0];
low[i]=dfn[0];
for (int j=head[i]; j!=-1; j=edge[j].nxt)
{
int t=edge[j].to;
if (t==fa[i])
continue;
if (vis[t])
{
low[i]=mymin(low[i], dfn[t]);
}
else
{
++child;
fa[t]=i;
tarjan(t);
low[i]=mymin(low[i], low[t]);
}
if (fa[i]!=0&&low[t]>=dfn[i])
{
if (!book[i])
book[i]=true, ++ans;
}
}
if (fa[i]==0&&child>=2)
{
if (!book[i])
book[i]=true, ++ans;
}
return;
}
int main()
{
#if yycoi==1
freopen("tmp.in", "r", stdin);
freopen("tmp.out", "w", stdout);
#endif // yycoi
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i)
head[i]=-1;
for (int i=1; i<=m; ++i)
{
int f, t;
scanf("%d%d", &f, &t);
add_edge(f, t);
add_edge(t, f);
}
for (int i=1; i<=n; ++i)
if (!vis[i])
tarjan(i);
#if yycoi==2
for (int i=1; i<=n; ++i)
printf("dfn[%d]=%d, low[%d]=%d\n", i, dfn[i], i, low[i]);
#endif // yycoi
printf("%d\n", ans);
for (int i=1; i<=n; ++i)
if (book[i])
printf("%d\n", i);
return 0;
}
回复
共 19 条回复,欢迎继续交流。
正在加载回复...