学步园

题意:

求对一个图补充最少的边使得其成为强连通图.

思路:

缩点是想到了,但是一是对"缩点"认识不够清晰,统计入度出度的时候想着想着又想成了实际的"点",于是就纠结在"不连通的强连通分量没有入度或出度为零的点",然后甚觉错误...

其实啊,"shrink"的时候判断的是一条边两边的id是否相同,这已经是将强连通分量视为一个点了...

一句话, 统计缩点之后的图中入度为零的点的个数, 出度为零的点的个数, 取其大即为答案. 因为从叶子连到根的有向边的条数不会超过这个数, 如果图是不连通的, 将每一个子图先处理成一叶一根(可保持收支平衡),然后首尾相接,仍然是不超过最大叶/根数.

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 20005;
const int MAXE = 50005;
struct pool
{
    int v,pre;
}p[MAXE];
int num,head[MAXN];
int dfn[MAXN],low[MAXN],id[MAXN],in[MAXN],out[MAXN];
bool vis[MAXN];
int size,Index,n,m;
stack<int> s;

void clear()
{
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    memset(dfn,0,sizeof(dfn));
    memset(head,0,sizeof(head));
    memset(p,0,sizeof(p));
    memset(vis,false,sizeof(vis));
    size = Index = num = 0;
    while(!s.empty()) s.pop();
}

void add(int u, int v)
{
    p[++num].v = v;
    p[num].pre = head[u];
    head[u] = num;
}

void Tarjan(int u)
{
    low[u] = dfn[u] = ++Index;
    vis[u] = true;
    s.push(u);
    for(int tmp = head[u],k;k = p[tmp].v,tmp;tmp = p[tmp].pre)
    {
        if(!dfn[k])
        {
            Tarjan(k);
            low[u] = min(low[u],low[k]);
        }
        else if(vis[k])
            low[u] = min(low[u],low[k]);
    }
    if(dfn[u]==low[u])
    {
        size++;
        int k;
        do
        {
            k = s.top();s.pop();
            vis[k] = false;
            id[k] = size;
        }while(k!=u);
    }
}

void shrink()
{
    for(int i=1;i<=n;i++)
        for(int tmp = head[i],k;k = p[tmp].v,tmp;tmp = p[tmp].pre)
            if(id[i]!=id[k])
            {
                in[id[k] ]++;
                out[id[i] ]++;
            }
}//对"缩点"认识不够彻底啊...

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        clear();//唉唉唉...
        scanf("%d %d",&n,&m);
        for(int i=0,u,v;i<m;i++)
        {
            scanf("%d %d",&u,&v);
            add(u, v);
        }
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i])
            {
                Tarjan(i);
            }
        }
        shrink();
        int in0 = 0, out0 = 0;
        for(int i=1;i<=size;i++)
        {
            if(!in[i])  in0++;
            if(!out[i]) out0++;
        }
        printf("%d\n",(size==1)?0:max(in0,out0));
    }
}