CodeChef Counting on a directed graph
Counting on a directed graph Problem Code: GRAPHCNT
Read problems statements in Mandarin Chineseand Russian.
Given an directed graph with N nodes (numbered from 1 to N) and M edges, calculate the number of unordered pairs (X, Y) such there exist two paths, one from node 1 to node X, and another one from node 1 to node Y, such that they don't share any node except node 1.
Input
There is only one test case in one test file.
The first line of each test case contains two space separated integers N, M. Each of the next M lines contains two space separated integers u, v denoting a directed edge of graph G, from node u to node v. There are no multi-edges and self loops in the graph.
Output
Print a single integer corresponding to the number of unordered pairs as asked in the problem..
Constraints and Subtasks
- 1 ≤ N ≤ 105
- 0 ≤ M ≤ 5 * 105
Subtask 1: (30 points)
- The graph is a Directed Acyclic Graph (DAG)i.e. there is no cycle in the graph.
Subtask 2: (20 points)
- N * M ≤ 50000000
Subtask 3 (50 points)
- No additional constraints
Example
Input:
6 6
1 2
1 3
1 4
2 5
2 6
3 6 Output:
14
Explanation
There are 14 pairs of vertices as follows:
(1,2)
(1,3)
(1,4)
(1,5)
(1,6)
(2,3)
(2,4)
(2,6)
(3,4)
(3,5)
(3,6)
(4,5)
(4,6)
(5,6)
Author:5★ztxz16
Tester:7★kevinsogo
Editorial:http://discuss.codechef.com/problems/GRAPHCNT
Tags:dominatormay15medium-hardztxz16
Date Added:25-03-2015
Time Limit:2 secs
Source Limit:50000 Bytes
Languages:ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC
题意:
https://s3.amazonaws.com/codechef_shared/download/translated/MAY15/mandarin/GRAPHCNT.pdf
分析:
建出支配树,然后统计1号节点的每个儿子内部点对数量,这就是不合法的点对数量,用总的点对数量减去不合法的就好了...
代码:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std; const int maxn=100000+5,maxm=500000+5; int n,m,tot,f[maxn],fa[maxn],id[maxn],dfn[maxn],siz[maxn],node[maxn],semi[maxn],idom[maxn];
long long ans; stack<int> dom[maxn]; struct M{ int cnt,hd[maxn],to[maxm],nxt[maxm]; inline void init(void){
cnt=0;
memset(hd,-1,sizeof(hd));
} inline void add(int x,int y){
to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;
} }G,tr; inline bool cmp(int x,int y){
return dfn[semi[x]]<dfn[semi[y]];
} inline int find(int x){
if(f[x]==x)
return x;
int fx=find(f[x]);
node[x]=min(node[f[x]],node[x],cmp);
return f[x]=fx;
} inline void dfs(int x){
dfn[x]=++tot;id[tot]=x;
for(int i=tr.hd[x];i!=-1;i=tr.nxt[i])
if(!dfn[tr.to[i]])
dfs(tr.to[i]),fa[tr.to[i]]=x;
} inline void LT(void){
dfs(1);dfn[0]=tot<<1;
for(int i=tot,x;i>=1;i--){
x=id[i];
if(i!=1){
for(int j=G.hd[x],v;j!=-1;j=G.nxt[j])
if(dfn[G.to[j]]){
v=G.to[j];
if(dfn[v]<dfn[x]){
if(dfn[v]<dfn[semi[x]])
semi[x]=v;
}
else{
find(v);
if(dfn[semi[node[v]]]<dfn[semi[x]])
semi[x]=semi[node[v]];
}
}
dom[semi[x]].push(x);
}
while(dom[x].size()){
int y=dom[x].top();dom[x].pop();find(y);
if(semi[node[y]]!=x)
idom[y]=node[y];
else
idom[y]=x;
}
for(int j=tr.hd[x];j!=-1;j=tr.nxt[j])
if(fa[tr.to[j]]==x)
f[tr.to[j]]=x;
}
for(int i=2,x;i<=tot;i++){
x=id[i];
if(semi[x]!=idom[x])
idom[x]=idom[idom[x]];
}
idom[id[1]]=0;
} signed main(void){
tr.init();G.init();
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;i++)
scanf("%d%d",&x,&y),tr.add(x,y),G.add(y,x);
for(int i=1;i<=n;i++)
f[i]=node[i]=i;
LT();ans=1LL*tot*(tot-1);
for(int i=tot;i>=2;i--){
siz[id[i]]++;
if(idom[id[i]]!=1)
siz[idom[id[i]]]+=siz[id[i]];
else
ans-=1LL*siz[id[i]]*(siz[id[i]]-1);
}
ans>>=1;
printf("%lld\n",ans);
return 0;
}
By NeighThorn
最新文章
- Sql常用语句(3)
- MVC的理解
- P1072 Hankson 的趣味题
- JavaEE 7技术一览
- HDU 1254
- Java for LeetCode 153 Find Minimum in Rotated Sorted Array
- VisualStudio2013Preview对C++11的支持(转载)
- Activity间切换的动画应用
- Whitelabel Error Page 专题
- 第五周博客作业<;西北师范大学|李晓婷>;
- Servlet(2)
- MySQL主从同步问题
- bzoj 3560 DZY Loves Math V - 线性筛 - 扩展欧几里得算法
- python-opencv 图像二值化,自适应阈值处理
- Java内存管理(一):深入Java内存区域
- java学习笔记—JDBC1(16)
- SCADA 必备函数之 :关于消息的函数
- Range(转)
- Spring IOC的配置使用
- 单个回调函数中返回多个Request以及Item