POJ1236【Tarjan+缩点】

题目大意：有向关系体现在电脑可以通过网络单向的传输文件，并规定一旦有电脑存在该文件，那么所有它能传输的电脑就能在第一时间得到这个文件，题目有两个问题，第一个是最少向网络中的几台电脑投放文件，能使得整个图中的电脑都得到文件，第二个问题是要最少再连接几条边，使得任意向图中一点投放文件，其他所有电脑都能得到文件。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<vector>
#define MAX 100+10
using namespace std;
vector<int> gra[MAX], N_gra[MAX];
int dfn[MAX];
int low[MAX];
int stack[MAX];
int scc[MAX];
int on_stack[MAX];
int Time;
int sta_index;
int scc_index;
int n;
int ind[MAX];
int out[MAX];

void Init() {
    memset(ind, 0, sizeof(ind));
    memset(out, 0, sizeof(out));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(on_stack, 0, sizeof(on_stack));
    memset(stack, 0, sizeof(stack));
    Time = 0;
    sta_index = 0;
    scc_index = 0;
}

void Tarjan(int u) {
    dfn[u] = low[u] = ++Time;
    stack[sta_index++] = u;
    on_stack[u] = 1;
    for (size_t i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if (!dfn[v]) {
            Tarjan(v);
            if (low[v] < low[u])
                low[u] = low[v];

        }

        else if (on_stack[v] && dfn[v] < low[u]) {
            low[u] = dfn[v];
        }
    }
    if (low[u] == dfn[u]) {
        int tmp = 0;
        scc_index++;
        while (u != tmp) {
            tmp = stack[--sta_index];
            on_stack[tmp] = 0;
            scc[tmp] = scc_index;
        }
    }
    return;
}

void Find_all_scc() {
    Init();
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            Tarjan(i);

        }

    }
    //缩点
    for (int i = 1; i <= n; i++) {
        for (size_t j = 0; j < gra[i].size(); j++) {
            int k = gra[i][j];
            if (scc[i] != scc[k]) {
                ind[scc[k]]++;
                out[scc[i]]++;
                N_gra[scc[i]].push_back(scc[k]);
            }

        }

    }

}

int main(void) {

    scanf("%d", &n);
    int t;
    for (size_t i = 0; i < n; i++) {
        gra[i].clear();
        N_gra[i].clear();

    }
    for (int i = 1; i <= n; i++) {
        while (scanf("%d", &t) && t) {
            gra[i].push_back(t);

        }

    }

    Find_all_scc();
    if (scc_index == 1) {
        printf("1\n0\n");
        return 0;

    }
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= scc_index; i++) {
        if (ind[i] == 0)
            ans1++;
        if (out[i] == 0)
            ans2++;
    }
    printf("%d\n%d\n", ans1, max(ans1, ans2));
    return 0;
}

巴特西

POJ1236【Tarjan+缩点】

最新文章

热门文章