原题链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2288

题意：

给你一个有向图，问你至少需要添加多少条边，使得整个图强连通。

题解：

就。。直接缩点，令缩点后入度为0的点有a个，出度为0的点有b个，答案就是max(a,b)

代码：

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<stack>

#define MAX_N 20004

using namespace std;

vector<int> G[MAX_N];

int dfn[MAX_N],low[MAX_N],ind;

bool vis[MAX_N];

stack<int> st;

bool inStack[MAX_N];

int id[MAX_N],tot=;

vector<int> newG[MAX_N];

vector<int> newrG[MAX_N];

int n,m;

void init() {

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

        G[i].clear();

        newG[i].clear();

        newrG[i].clear();

    }

    memset(dfn, , sizeof(dfn));

    memset(low, , sizeof(low));

    ind = tot = ;

    memset(vis, , sizeof(vis));

    while (st.size())st.pop();

    memset(inStack, , sizeof(inStack));

    memset(id, , sizeof(id));

}

void Tarjan(int u) {

    dfn[u] = low[u] = ++ind;

    st.push(u);

    inStack[u] = ;

    vis[u] = ;

    for (int i = ; i < G[u].size(); i++) {

        int v = G[u][i];

        if (!vis[v]) {

            Tarjan(v);

            low[u] = min(low[u], low[v]);

        }

        else if (inStack[v])

            low[u] = min(low[u], dfn[v]);

    }

    if (low[u] == dfn[u]) {

        tot++;

        int t;

        do {

            t = st.top();

            st.pop();

            inStack[t] = ;

            id[t] = tot;

        } while (t != u);

    }

}

int main() {

    int T;

    cin.sync_with_stdio(false);

    cin >> T;

    while (T--) {

        cin >> n >> m;

        int ans = ;

        init();

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

            int u, v;

            cin >> u >> v;

            G[u].push_back(v);

        }

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

            if (!vis[i])Tarjan(i);

        for (int u = ; u <= n; u++)

            for (int i = ; i < G[u].size(); i++)

                if (id[u] != id[G[u][i]]) {

                    newG[id[u]].push_back(id[G[u][i]]);

                    newrG[id[G[u][i]]].push_back(id[u]);

                }

        if (tot == ) {

            cout <<  << endl;

            continue;

        }

        int a = , b = ;

        for (int u = ; u <= tot; u++) {

            if (newG[u].size() == )a++;

            if (newrG[u].size() == )b++;

        }

        cout << max(a, b) << endl;

    }

    return ;

}

巴特西

UvaLive 4287 Proving Equivalences 强连通缩点

题意：

题解：

代码：

最新文章

热门文章