【题意】

给定一个有向图,问图中互相可达(强连通)的点有多少对

【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 ;
}

最新文章

  1. zabbix监控系列(3)之zabbix触发器格式配置
  2. jquery.validation.js 表单验证
  3. Navicat(服务器对象) -2之MySQL 或 MariaDB 对象
  4. scrollTop 鼠标往下移动到一定位置显示隐藏
  5. HDU 4483 Lattice triangle(欧拉函数)
  6. Contest20140906 反思
  7. HTML之学习笔记(十一)其它标签
  8. Ehcache详细解读(转)
  9. spring-session 2.0 实现细节
  10. rpc概念及nfs的基本应用
  11. 如何在css中设置按钮button中包含图片文字对齐方式
  12. MySQL_join连接
  13. RocketMQ源码分析:(一)安装与案例演示
  14. POJ1580 水题,积累!
  15. Java中CAS详解
  16. 2018-2019-2 20165330《网络对抗技术》Exp2 后门原理与实践
  17. php连接微软MSSQL(sql server)完全攻略
  18. Vue项目中引用vue-resource步骤
  19. configuration on ubuntu server
  20. oracle中vsize和length

热门文章

  1. ECshop安装提示cls_image::gd_version() 和不支持JPEG
  2. 2018.3.31 java中的递归
  3. IntelliJ IDEA java设置程序运行时内存
  4. shell脚本,awk取奇数行与偶数行方法。
  5. 如何用VS2017用C++语言写Hello world 程序?
  6. VB6 代码编辑页面添加支持滚轮模式
  7. Windows7设置局域网文件共享
  8. python面试题之python多线程与多进程的区别
  9. python之序列化
  10. LeetCode(234) Palindrome Linked List