Proving Equivalences 【HDU-2767】强连通分量+Tanjar缩点
传送门
题意:问至少增加多少有向边能将图变成强连通图?
思路:如果存在强连通分量,那么我们可以将这个分量看作一个点(一个点也是强连通分量),利用tanjar缩点将原本复杂的图转化为多个DAG如何将这些DAG连接起来变成强连通图呢?ans=max(入度=0点的数量,出度=0点的数量) ///特殊情况:原本本身就是一个强连通图ans=0。
问什么答案是那样的?你要将图连接成强连通的,那么入度为0的点肯定至少有一条边要连接它,出度为0的点肯定也有一条边要连接它,我们可以将一个出度为0的点连接入度为0的点,那么连接线的数量就是max(入度=0点的数量,出度=0点的数量)。
这是我自己画的图(缩点后的DAG图),自己动手画一下就会得到答案。
左:入度为0:4 出度为0:1 ans=4
右:入度为0:2 出度为0:6 ans=6
代码:
///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>
#define MT(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const double E=2.718281828459;
const ll mod=998424353;
const double INF=1e15;
int n,m;
struct node
{
int e;
int p;
}load[50005],edge[50005];
int head[20005],tail[20005],sign;
int dfn[20005],low[20005],time;
int stack_[20005],instack[20005];
int top,cnt;
int belong[20005];
int in[20005],out[20005];
void init()
{
sign=top=cnt=time=0;
for(int i=0;i<=n;i++)
{
tail[i]=head[i]=-1;
instack[i]=dfn[i]=low[i]=0;
in[i]=out[i]=0;
}
}
void add_edge(int s,int e)
{
load[++sign]=node{e,head[s]};
head[s]=sign;
}
void tanjar(int s)
{
dfn[s]=low[s]=++time;
instack[s]=1;
stack_[++top]=s;
int e;
for(int i=head[s];i!=-1;i=load[i].p)
{
e=load[i].e;
if(!dfn[e])
{
tanjar(e);
low[s]=min(low[s],low[e]);
}
else
{
if(instack[e])
low[s]=min(low[s],dfn[e]);
}
}
int t;
if(dfn[s]==low[s])
{
cnt++;
do
{
t=stack_[top--];
instack[t]=0;
belong[t]=cnt;
}while(t!=s);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int s,e;
scanf("%d %d",&n,&m);
init();
for(int i=1;i<=m;i++)
{
scanf("%d %d",&s,&e);
add_edge(s,e);
}
///Tanjar缩点
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tanjar(i);
}
sign=0;
int a,b;
///重新建图
for(int i=1;i<=n;i++)
{
for(int j=head[i];j!=-1;j=load[j].p)
{
e=load[j].e;
a=belong[i];
b=belong[e];
if(a!=b)
{
edge[++sign]=node{b,tail[a]};
tail[a]=sign;
}
}
}
///计算出度入度为0点的数量
for(int i=1;i<=cnt;i++)
{
for(int j=tail[i];j!=-1;j=edge[j].p)
{
e=edge[j].e;
out[i]=1;
in[e]=1;
}
}
int x=0,y=0;
for(int i=1;i<=cnt;i++)
{
if(out[i]==0)
x++;
if(in[i]==0)
y++;
}
///如果本身就是一个强连通图,ans=0
printf("%d\n",(cnt==1)?0:max(x,y));
}
return 0;
}