萌新强连通分量求调,RE啊
查看原帖
萌新强连通分量求调,RE啊
405146
Ruan_ji楼主2024/7/21 10:29

不知道为啥RE,下了一组数据如下

输入:

5
2 4 3 0
4 5 0
0
0
1 0

输出:

1
2

我的输出:不输出

挑灯夜战萌新已经快疯,恳请大佬帮我。

测试信息: 测试信息

附上有注释的代码:

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>

#define MAXN 5000005

using namespace std;

int n;
vector<int> oldG[MAXN]; //老G是原图
vector<int> G[MAXN]; //缩点之后的图

//强连通分量的变量们
int dfn[MAXN], low[MAXN]; 
int scccnt, scc[MAXN];
int sum; 
stack<int> s;

int in[MAXN], out[MAXN]; //缩完点之后的图的每个点的出度和入度
int vis1[MAXN], vis2[MAXN]; //分别标记这个点有没有被统计答案过(在最后面用了)

void tarjan(int u) {
    dfn[u] = low[u] = ++sum;
    s.push(u);
    for (int i = 0; i < oldG[u].size(); ++i) {
        int v = oldG[u][i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else {
            if (!scc[v]) {
                low[u] = min(low[u], low[v]);
            }
        }
    }

    if (dfn[u] == low[u]) { //形成强连通分量
        scccnt++;
        int v;
        do {
            v = s.top();
            s.pop();
            scc[v] = scccnt;
        } while (v != u) ;
    }
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int v;
        while (cin >> v) {
            if (v == 0) {
                break;
            }
            oldG[i].push_back(v);
        }
    }


    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < oldG[i].size(); ++j) {
            if (scc[i] != scc[ oldG[i][j] ]) {
                G[scc[i]].push_back(scc[oldG[i][j]]);
                in[ scc[G[i][j]] ] += 1;
                out[scc[i]] += 1;
            } //缩点之后建图
        }
    } 

    int ans1 = 0, ans2 = 0;
    bool vis = 0;
    for (int i = 2; i <= n; ++i) {
        if (scc[i] != scc[i-1]) {
            vis = 1;
            break;
        }
    } //特判,如果只有一个强连通分量
    if (vis == 0) {
        cout << 1 << endl << 0 << endl;
        return 0;
    }

    //正常统计出入度并输出答案
    for (int i = 1; i <= n; ++i) {
        if (!in[scc[i]] && !vis1[scc[i]]) ans1++, vis1[scc[i]] = 1;
        if (!out[scc[i]] && !vis2[scc[i]]) ans2++, vis2[scc[i]] = 1;
    }

    cout << ans1 << endl << max(ans1, ans2) << endl;
    return 0;
}

小菊弱感激不尽!!!

2024/7/21 10:29
加载中...