HDU 2767:Proving Equivalences(强连通）

题意：

一个有向图，问最少加几条边，能让它强连通

方法：

1：tarjan 缩点

2：采用如下构造法：

缩点后的图找到所有头结点和尾结点，那么，可以这么构造：把所有的尾结点连一条边到头结点，就必然可以是强连通了。如果说有几个结点不连通，那么让他们的尾结点相互只向对方的头结点就好了。

那么，最后的答案就是，头结点和尾结点中比较小的那个数量。

当然，如果缩点后只有一个点，那么就是0;

代码：

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

#define N 20010

using namespace std;

vector <int> to[N];

vector <int> g[N];

int in[N], out[N];

//#define vii vector<int>iterator;

int low[N], dep[N], id[N], s[N], top, scnt, cnt;

int n, m;

void tarinit() {

    top = cnt = scnt = ;

    memset(dep, -, sizeof(dep));

}

void tarjan(int u) {

    int minc = low[u] = dep[u] = cnt++;

    s[top++] = u;

    int end = to[u].size();

    for (int i = ; i < end; i++) {

        if (dep[to[u][i]] == -) tarjan(to[u][i]);

        if (minc > low[to[u][i]]) minc = low[to[u][i]];

    }

    if (minc < low[u]) low[u] = minc;

    else {

        while (s[top] != u){

            id[s[--top]] = scnt;

            low[s[top]] = n+;

        }

        scnt++;

    }

}

int main() {

    int t;

    scanf("%d", &t);

    while (t--) {

        scanf("%d%d", &n, &m);

        for (int i = ; i <= n; i++) to[i].clear(), g[i].clear();

        for (int i = ; i < m; i++) {

            int u, v;

            scanf("%d%d", &u, &v);

            to[u].push_back(v);

        }

        tarinit();

        for (int i = ; i <= n; i++) {

            if (dep[i] == -) {

                tarjan(i);

            }

        }

        memset(out,,sizeof(out));

        memset(in,,sizeof(in));

        for (int i = ; i <= n; i++) {

            int end = to[i].size();

            for (int j = ; j < end; j++) {

                if (id[i] != id[to[i][j]]) {

                    out[id[i]]++;

                    in[id[to[i][j]]]++;

                }

            }

        }

        if (scnt == )  {

            puts("");

            continue;

        }

        int root = ;

        int leaf = ;

        for (int i = ; i < scnt; i++) {

            if (out[i] == ) leaf++;

            if (in[i] == ) root++;

        }

        printf("%d\n", max(root,leaf));

    }

    return ;

}

巴特西

HDU 2767:Proving Equivalences(强连通）

最新文章

热门文章