P2341 [HAOI2006]受欢迎的牛
2024-08-29 02:39:52
塔尔羊标准模板(我才不会告诉你我嘴里含着一个九省联考的出题人)
不会劈配、林克卡特树、制胡窜
我还会叉粪宿主,梳妆素组,西安段素
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>line[50000];
int dfn[10100],low[10100],tim;
bool instack[10100];
int stack[101000],top;
int belong[10100],cnt;
int num[10100];
int cot[10100];
void tarjan(int now)
{
dfn[now]=low[now]=++tim;
stack[++top]=now;
instack[now]=true;
for(int i=0;i<line[now].size();i++)
{
int nxt=line[now][i];
if(!dfn[nxt])
{
tarjan(nxt);
low[now]=min(low[nxt],low[now]);
}
else
if(instack[nxt]&&dfn[nxt]<low[now])
low[now]=dfn[nxt];
}
if(low[now]==dfn[now])
{
int pas;
cnt+=1;
do
{
pas=stack[top--];
instack[pas]=false;
belong[pas]=cnt;
num[cnt]+=1;
}while(pas!=now);
}
return ;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
line[a].push_back(b);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=n;i++)
for(int j=0;j<line[i].size();j++)
if(belong[i]!=belong[line[i][j]])
cot[belong[i]]=1;
int ans=0;
int pas;
for(int i=1;i<=cnt;i++)
if(!cot[i])
ans+=1,pas=i;
if(ans==1)
printf("%d",num[pas]);
else
printf("0");
return 0;
}
日常赛高
最新文章
- C# 记录错误日志
- css知多少(9)——float下篇
- General protection fault Exceptions in Linux/IA32 Systems
- asp.net实现通用水晶报表
- Spark学习笔记--Transformation 和 action
- DotNetBar v11.4.0.6 Fully Cracked
- nefu 197 关键字检索(kmp算法)
- 学习总结------用JDBC连接MySQL
- 解决jenkins下使用HTML Publisher插件后查看html报告显示不正常 以jmeter报告为例
- 2017CCPC 网络选拔赛1003 Ramsey定理
- 【C++】C++未定义行为
- Python开发【笔记】:aiohttp搭建简易聊天室
- idea 与springboot 快捷键
- mysql dbcp Caused By: com.mysql.jdbc.exceptions.jdbc4.CommunicationsException: The last packet successfully received
- Python2.7-fileinput
- Add Again UVA - 11076(排列之和)
- php获取网址
- maven 插件在线安装
- Centos7 配置ssh 免秘钥登陆
- 2018.09.11 poj2976Dropping tests(01分数规划)