这道题巩固一下Tarjan求强连通分量(最近没有更新图论的算法，天天比赛+总结，等开学就更)，自己写了一下感觉还可以hiahiahia！

 

题目大意：给你几组 等价公式 问至少还要加几组公式，使得这些公式可以任意之间推出来，比如说a->b,b->c，你只需要加一组c->a就可以实现任意公式之间的互推。用图论的思想来理解的话，其实就是 加几条边 可以使当前的一张图成为强连通图。

我们可以这么想：

第一步：强连通图有什么性质，因为他任意点之间可以联通，所以任意点都有一个出度与入度，就是都有指向他的边，和他指向的边。所以我们只需要判断，有多少个出度为0的点，和多少个入度为0的点，他俩之间取一个最大值，为什么取最大值，因为必须要满足 出度不为0&&入度也不为0，因为如果一个点入度为0，这张图绝对不是强连通图。这个连接是证明->证明强连通图出度与入度为0(博主看见别打我，我只是引用)

第二步：因为一个强连通分量里面的点都是可以相互到达的并且这里面的点入度与出度绝不=0，因为这是强连通分量！所以我们把这这些点看做一个点 。

第三步： 判断每一条边，如果这条边连接的这两个点，分别属于不同的强联通分量，则说明这两个强连通分量之间有边相连，因为我们已经把强连通分量看做一个点，假如 a->b，我们让Scc[b]的入度++，让Scc[a]的出度++，到最后看每个强连通分量的出度和入度，indx标记入度为0，outdx标记出度为0，最后结果就是max(indx,outdx)。

 

附一下代码+注释：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
#include <stdlib.h>
#include <time.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const ll INF=1e9;
/*坚持不懈，无懈可击*/
int Scc[maxn],sig;//记录强连通分量
int Sta[maxn],top;//栈
int dfn[maxn],low[maxn];//两个时间戳
int head[maxn];
int ind[maxn],outd[maxn];//记录强连通分量的入度与出度
struct node{int e,next;}edge[maxn];
ll cnt=0,snt=0;//snt记录时间戳
void restart()
{
    mem(head,-1);mem(low,0);
    mem(dfn,0);mem(Scc,0);
    mem(Sta,0);top=0;
    cnt=0,sig=0;snt=0;
    mem(ind,0);mem(outd,0);
}
void addedge(int u,int v)
{
    edge[cnt]=node{v,head[u]};
    head[u]=cnt++;
}
void dfs(int u)
{
    low[u]=dfn[u]=++snt;
    Sta[top++]=u;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int e=edge[i].e;
        if(dfn[e]==0)
        {
            dfs(e);
            low[u]=MIN(low[u],low[e]);
        }
        else if(Scc[e]==0)
            low[u]=MIN(dfn[e],low[u]);
    }
    if(low[u]==dfn[u])//发现根节点u下面的强连通分量
    {
        sig++;
        while(1)
        {
            int x=Sta[--top];//出栈
            Scc[x]=sig;
            if(x==u) break;
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        restart();
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int sn,en;
            scanf("%d%d",&sn,&en);
            addedge(sn,en);
        }
        for(int i=1;i<=n;i++)
            if(dfn[i]==0) dfs(i);
        for(int i=1;i<=n;i++)
            for(int k=head[i];k!=-1;k=edge[k].next)
            {
                int e=edge[k].e;
                if(Scc[i]!=Scc[e])//缩点操作
                {
                    ind[Scc[e]]++;//强连通分量的入度与出度
                    outd[Scc[i]]++;
                }
            }
        int indx=0,outdx=0;
        for(int i=1;i<=sig;i++)//扫描每一个强连通分量的入度与出度就可以了
        {
            if(ind[i]==0) indx++;
            if(outd[i]==0) outdx++;
        }
        if(sig==1)//注意特判条件，如果图就是强连通图不需要加边
            printf("0\n");
        else
            printf("%d\n",MAX(indx,outdx));
    }
    return 0;
}

心得：缩点操作降低了时间复杂度，而不用每一个点去考虑，从而大大降低了时间复杂度，如果给你100000个点，去考虑每一个点的出度与入度，复杂度O(1000000)，但是如果这个图被分为了两个强连通分量，那最后只需要统计 2 次，这个复杂度优化差足以说明缩点操作的效率！以后尽可能的缩点！加油