题目描述
相当于是把对强连通分量的连通换成了半联通。
让你求最大半联通图中点的数目和一共有多少个最大半联通子图
数据范围:
$1≤N≤105$,
$1≤M≤106$,
$1≤X≤108$
样例
输入:
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
输出:
3
3
经过仔细思考我们不难发现,强连通分量必定是半联通的
举个例子
环 1 —> 2 — > 3 —>1 显然是一个强连通分量
我们在该环中不难找到一个最大半联通子图 1 – > 2 –> 3 或者 2 –> 3 –> 1
我们又知道,一个图处理完强连通向量后,如果将一个强连通向量看成一个点,那么整个图就是一个拓扑图(DAG)
经过观察发现,处理完后得到的DAG图上的每一条链都可以看作是一个半联通子图
于是,第一个问题便转化成了在DAG上求最长链中点的数目
第二个问题便转化成了在DAG上求有多少条最长链,及图中最长链的数目
注意!!还没有完
在转化得到的DAG图中,每个”点”之间可能连了多条边,这会使我们在求有多少条最长链时出现错误!!
所以,我们需要借助hash表来判重!!
参考文献
Y总的视频 XD
C++ 代码
首先是默写一遍求强连通分量的模板
void tarjan(int u)
{
dfn[u] = low[u] = ++ times ;
stk[++ top] = u,in_stk[u] =true;
for(int i =h[u]; ~i;i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u],low[j]);
}
else if(in_stk[j]) low[u] = min(low[u] , dfn[j]);
}
if(dfn[u] == low[u])
{
scc_cnt ++;
int y;
do{
y = stk[top --];
in_stk[y] = false;
id[y] = scc_cnt;
Size[scc_cnt] ++;
}while(y != u);
}
}
接着,对连着两个不同强连通分量的边进行判重
unordered_set <LL> S;
for(int u = 1;u <= n;u ++)
{
for(int i = h[u]; ~i;i = ne[i])
{
int j = e[i];
int a = id[u],b = id[j];
LL hash = a * 1000000ll + b;//最多有1000000条边!!
if(a != b && !S.count(hash))
{
add(sh,a,b);
S.insert(hash);
}
}
}
计算以每个“点”(强连通分量)为终点的最长链中的点的数目和数量
for(int i = scc_cnt; i ;i --)
//由于编号更大的点所在的强连通分量总是更先被找到,且这里要保证顺序,所以我们要逆着循环!
{
if(! f[i])
{
f[i] = Size[i];
g[i] = 1;
}
for(int j = sh[i]; ~j ; j = ne[j])
{
int k = e[j];
if(f[k] < f[i] + Size[k])
{
f[k] = f[i] + Size[k];
g[k] = g[i];
}
else if(f[k] == f[i] + Size[k]) //如果以“点”的为终点的两条长链长度相同,那么将所得的的数目相加
g[k] = (g[k] + g[i]) % mod;//数目很多,记得要%mod哦
}
}
最后统计一下以哪个点为终点的长链的点的数目最多,将他所携带的点的数目和最长链数量揪出来
int maxn = 0 ,sum = 0;
for(int i = 1;i <= scc_cnt;i ++)
if(f[i] > maxn)
{
maxn = f[i];
sum = g[i];
}
else if(f[i] == maxn) sum = (sum + g[i]) % mod;//将其他点所携带的最长链数目相加!
完整代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <unordered_set>
using namespace std;
typedef long long LL;
const int N = 100010 , M = 2000010;
int h[N],sh[N],ne[M],e[M],idx;
int stk[N],top,times;
bool in_stk[N];
int dfn[N],low[N];
int id[N],scc_cnt,Size[N];
int f[N],g[N];
int n,m,mod;
void add( int h[],int a,int b)
{
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ times ;
stk[++ top] = u,in_stk[u] =true;
for(int i =h[u]; ~i;i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u],low[j]);
}
else if(in_stk[j]) low[u] = min(low[u] , dfn[j]);
}
if(dfn[u] == low[u])
{
scc_cnt ++;
int y;
do{
y = stk[top --];
in_stk[y] = false;
id[y] = scc_cnt;
Size[scc_cnt] ++;
}while(y != u);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&mod);
memset(h,-1,sizeof h);
memset(sh,-1,sizeof sh);
while(m -- )
{
int a,b;
scanf("%d%d",&a,&b);
add(h,a,b);
}
for(int i = 1;i <= n;i ++)
if(!dfn[i]) tarjan(i);
unordered_set <LL> S;
for(int u = 1;u <= n;u ++)
{
for(int i = h[u]; ~i;i = ne[i])
{
int j = e[i];
int a = id[u],b = id[j];
LL hash = a * 1000000ll + b;
if(a != b && !S.count(hash))
{
add(sh,a,b);
S.insert(hash);
}
}
}
for(int i = scc_cnt; i ;i --)
{
if(! f[i])
{
f[i] = Size[i];
g[i] = 1;
}
for(int j = sh[i]; ~j ; j = ne[j])
{
int k = e[j];
if(f[k] < f[i] + Size[k])
{
f[k] = f[i] + Size[k];
g[k] = g[i];
}
else if(f[k] == f[i] + Size[k])
g[k] = (g[k] + g[i]) % mod;
}
}
int maxn = 0 ,sum = 0;
for(int i = 1;i <= scc_cnt;i ++)
if(f[i] > maxn)
{
maxn = f[i];
sum = g[i];
}
else if(f[i] == maxn) sum = (sum + g[i]) % mod;
printf("%d\n%d\n",maxn,sum);
return 0;
}