codeforces 1037E. Trips(倒叙)
2024-10-01 21:04:07
解题思路:
正着搞好像有点恶心。
反着搞。
一边删一边搞,从崩坏的地方开始,入度--。
最后dfs崩坏,更新答案。
注意要把边删掉防止重复崩坏。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
struct pnt{
int hd;
int ind;
bool ded;
}p[];
struct ent{
int twd;
int lst;
}e[];
int cnt;
int n,m,k;
int lft;
int ans[];
int u[],v[];
void ade(int f,int t)
{
cnt++;
e[cnt].twd=t;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
p[f].ind++;
return ;
}
void Delete(int x)
{
if(p[x].ded)
return ;
p[x].ded=true;
lft--;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
p[to].ind--;
if(p[to].ind<k)
Delete(to);
}
return ;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);
ade(u[i],v[i]);
ade(v[i],u[i]);
}
lft=n;
for(int i=;i<=n;i++)
{
if(p[i].ind<k)
{
Delete(i);
}
}
for(int i=m;i;i--)
{
ans[i]=lft;
p[u[i]].hd=e[p[u[i]].hd].lst;
p[v[i]].hd=e[p[v[i]].hd].lst;
if(!p[v[i]].ded)
p[u[i]].ind--;
if(!p[u[i]].ded)
p[v[i]].ind--;
if(p[v[i]].ind<k)
Delete(v[i]);
if(p[u[i]].ind<k)
Delete(u[i]);
}
for(int i=;i<=m;i++)
printf("%d\n",ans[i]);
return ;
}
最新文章
- range()函数的使用
- C#字符串操作(參照圓友)
- 十、Java基础---------面向对象之抽象类与接口
- 自定义请求头信息及cookie信息
- Stackdump: 一个可以离线看stackoverflow的工具
- jQuery源码学习:使用隐藏的new来创建对象
- Poj 1269 Intersecting Lines_几何模板
- poj 1961 Period(KMP训练指南例题)
- linux怎样修改用户权限
- JSP内置对象之request
- 在Azure China用自定义镜像创建Azure VM Scale Set
- Luogu P1757 通天之分组背包
- Python学习笔记-EXCEL操作
- js 人民币小写金额转换为大写
- Django进阶-auth集成认证模块
- Mybatis关联查询之一对多和多对一XML配置详解
- vue-cli之webpack的proxyTable无效的解决方案
- PHP:第二章——PHP中的流程控制语句
- Velocity学习笔记
- 安装notepad++之后鼠标右键无Edit with notepad++