时间戳

首页 > 技术文章 > hdu 2767 Proving Equivalences

hdu 2767 Proving Equivalences

hxer 2016-02-10 23:18 原文

Proving Equivalences

题意:输入一个有向图(强连通图就是定义在有向图上的)，有n(1 ≤ n ≤ 20000)个节点和m(0 ≤ m ≤ 50000)条有向边；问添加几条边可使图变成强连通图；

强连通分量:对于分量中的任意两个节点，都存在一条有向的路径(顺序不同，表示的路径不同)；说白了，就是任意两点都能形成一个环(但不是说只有一个环)

思路:使用Tarjan算法 (讲解得很好)即可容易地在得到在一个强连通分量中设置每个点所属的强连通分量的标号；即得到所谓的缩点；
之后就是合并所有连通分量，使得形成一个强连通分量。这个合并就是在连通分量中加有向边，即将所缺少的总入度和缺少的总的出度比较，取大的即可；(可浪费不能缺)


实现细节:开始认为可以在Tarjan中之中得到每个强连通分量的入度和出度；即在循环枚举v时再加一个else来看这条连通分量之间的边，设置出度，入度在标记点的连通分量标号时处理。但是里面涉及到好几种情况的点；不好分析与调试；还是在全部处理完了再遍历边来看是否为不同连通分量的连边；更清晰一些；

PS:要特判id == 1的情况，不然题给就是一个强连通分量，ans = 0，但是处理in[],out[]时会认为该连通分量需要和其他的连通分量连边，导致答案为1...

还有就是点的入度和出度都是对所属的连通分量而言的，开始输入时不需要处理；

时间复杂度为O(n+m)

// 265MS    4792K
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
const int MAXN = 50050;
int head[MAXN],tot;
struct edge{
    int to,w,Next;
}e[MAXN];
void ins(int a,int b,int w = 0)
{
    e[++tot].Next = head[a];
    e[tot].to = b;
    e[tot].w = w;
    head[a] = tot;
}
const int N = 20020;
int pre[N],dfs_clock,low[N];
int belong[N],id;
stack<int> S;
bool stk[N];
void Tarjan(int u)
{
    pre[u] = low[u] = ++dfs_clock;
    S.push(u);
    stk[u] = true;
    int v;//点u所在连通分量的出度；
    for(int i = head[u];i;i = e[i].Next){
        v = e[i].to;
        if(pre[v] == 0){
            Tarjan(v);
            low[u] = min(low[u],low[v]);
        }else if(stk[v]){
            low[u] = min(low[u],pre[v]);
        }
    }
    if(pre[u] == low[u]){//强连通分量的根节点
        ++id;
        do{
            v = S.top();
            S.pop();stk[v] = false;
            belong[v] = id;
        }while(v != u);
    }
}
int in[N],out[N];
int main()
{
    int T,kase = 1;
    scanf("%d",&T);
    while(T--){
        MS0(head);tot = 0;
        int n,m,a,b;
        scanf("%d%d",&n,&m);
        rep0(i,0,m){
            scanf("%d%d",&a,&b);
            ins(a,b);
        }
        id = dfs_clock = 0;
        rep1(i,0,n) pre[i] = low[i] = belong[i] = 0;
        rep1(i,1,n)if(pre[i] == 0)
            Tarjan(i);
        rep1(i,1,id)
            in[i] = out[i] = 0;//并不是原图输入的入度与出度；而是缩点之后的强连通分量;
        rep1(u,1,n){//在缩点完了之后再对边进行处理，看是否符合入度出度关系；
            for(int index = head[u];index;index = e[index].Next){
                int v = e[index].to;
                if(belong[u] != belong[v]){//***强连通分量之间的连边
                    in[belong[v]]++,out[belong[u]]++;
                }
            }
        }
        int in_deg = 0,out_deg = 0;
        if(id == 1){// ** WA了很多次。。
            puts("0");
            continue;
        }
        rep1(j,1,id){            
            if(in[j] == 0) in_deg++;
            if(out[j] == 0) out_deg++;
        }        
        printf("%d\n",max(in_deg,out_deg));
    }
    return 0;
}

 

推荐阅读