[HAOI2006]受欢迎的牛(tarjan缩点)
2024-08-30 16:15:42
直接tarjan求scc,然后统计出度为0的缩点,如果多余1个就输出0,只有一个就输出这个缩点里的点。
——代码
#include <cstdio>
#include <cstring>
#include <stack> using namespace std; int n, m, cnt, idx, ans, k;
int next[], to[], head[], low[], dfn[], belong[], c[];
bool ins[];
stack <int> s; inline void add(int x, int y)
{
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
} inline void tarjan(int u)
{
low[u] = dfn[u] = ++idx;
s.push(u);
ins[u] = ;
int i, v;
for(i = head[u]; i != -; i = next[i])
{
v = to[i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(ins[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
cnt++;
do
{
v = s.top();
s.pop();
ins[v] = ;
belong[v] = cnt;
}while(u != v);
}
} int main()
{
int i, j, x, y, u, v;
memset(head, -, sizeof(head));
scanf("%d %d", &n, &m);
for(i = ; i <= m; i++)
{
scanf("%d %d", &x, &y);
add(x, y);
}
cnt = ;
for(i = ; i <= n; i++)
if(!dfn[i])
tarjan(i);
for(u = ; u <= n; u++)
for(i = head[u]; i != -; i = next[i])
{
v = to[i];
if(belong[u] != belong[v]) c[belong[u]]++;
}
for(i = ; i <= cnt; i++)
if(!c[i])
{
ans++;
k = i;
}
if(ans > ) printf("");
else
{
ans = ;
for(i = ; i <= n; i++)
if(belong[i] == k)
ans++;
printf("%d", ans);
}
return ;
}
最新文章
- Redis数据结构详解之Set(三)
- 定制sqlmap tamper脚本
- lua以xpcall实现try/catch功能
- php强制转换类型和CMS远程管理插件的危险
- RxJava学习入门
- Delphi下16进制位图数据转位图
- HDU 3265 扫描线(矩形面积并变形)
- UVA 11137 Ingenuous Cubrency(dp)
- js毫秒数转换成时间格式
- Qt之自定义搜索框
- iOS 2D绘图详解(Quartz 2D)之Bitmap
- 每天一道面试题(2):实现strncpy
- hdu 1863 畅通工程(最小生成树,基础)
- JS 实现地区,省份,城市,县区4级联动
- bzoj 1923 [Sdoi2010]外星千足虫(高斯消元+bitset)
- jboss部署应用
- 玩sdr的朋友们,在rtl_tcp时,记得调整rtl_AGC和tuner_AGC啊
- 【翻译自mos文章】回收 asm磁盘空间的方法
- Docker Stack 集群部属服务
- PDF 补丁丁 0.6.0.3427 版发布(修复提取图片问题)