【CCF】高速公路 tarjan强连通缩点
2024-09-06 03:52:11
【题意】
给定一个有向图,问图中互相可达(强连通)的点有多少对
【AC】
强连通缩点,缩点后是一个DAG,所以互相可达的点只在强连通块里。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm> using namespace std;
int n,m;
const int maxn=1e4+;
const int maxm=1e5+;
struct edge{
int to;
int nxt;
}e[maxm];
int head[maxn];
int tot;
int S[maxn],top;
int dfn[maxn],low[maxn],id;
int belong[maxn],num;
bool vis[maxn];
int circle[maxn];
void init(){
memset(head,-,sizeof(head));
tot=;
id=top=num=;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vis,false,sizeof(vis));
memset(circle,,sizeof(circle));
}
void add(int u,int v){
e[tot].to=v;
e[tot].nxt=head[u];
head[u]=tot++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++id;
S[++top]=u;
vis[u]=true;
for(int i=head[u];i!=-;i=e[i].nxt)
{
int v=e[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
num++;
while()
{
belong[S[top]]=num;
vis[S[top]]=false;
if(S[top--]==u) break;
}
}
} int main(){
while(~scanf("%d%d",&n,&m)){
init();
int u,v;
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=;i<=n;i++){
circle[belong[i]]++;
}
int ans=;
for(int i=;i<=num;i++){
ans+=circle[i]*(circle[i]-)/;
}
printf("%d\n",ans);
}
return ;
}
最新文章
- zabbix监控系列(3)之zabbix触发器格式配置
- jquery.validation.js 表单验证
- Navicat(服务器对象) -2之MySQL 或 MariaDB 对象
- scrollTop 鼠标往下移动到一定位置显示隐藏
- HDU 4483 Lattice triangle(欧拉函数)
- Contest20140906 反思
- HTML之学习笔记(十一)其它标签
- Ehcache详细解读(转)
- spring-session 2.0 实现细节
- rpc概念及nfs的基本应用
- 如何在css中设置按钮button中包含图片文字对齐方式
- MySQL_join连接
- RocketMQ源码分析:(一)安装与案例演示
- POJ1580 水题,积累!
- Java中CAS详解
- 2018-2019-2 20165330《网络对抗技术》Exp2 后门原理与实践
- php连接微软MSSQL(sql server)完全攻略
- Vue项目中引用vue-resource步骤
- configuration on ubuntu server
- oracle中vsize和length
热门文章
- ECshop安装提示cls_image::gd_version() 和不支持JPEG
- 2018.3.31 java中的递归
- IntelliJ IDEA java设置程序运行时内存
- shell脚本,awk取奇数行与偶数行方法。
- 如何用VS2017用C++语言写Hello world 程序?
- VB6 代码编辑页面添加支持滚轮模式
- Windows7设置局域网文件共享
- python面试题之python多线程与多进程的区别
- python之序列化
- LeetCode(234) Palindrome Linked List