Tarjan全WA求助

qfpjm @ 2021-08-09 08:53:54

#include <bits/stdc++.h>

using namespace std;

struct edge
{
    int u, v;
};

int n, m, dfn[100005], low[100005], cnt, cnt2;
bool in[100005];
vector<edge> G[100005];
vector<int> ans[100005];
stack<int> s;

void Tarjan(int u)
{
    cnt ++;
    low[u] = cnt;
    dfn[u] = cnt;
    in[u] = true;
    s.push(u);
    for (int i = 0 ; i < G[u].size() ; i ++)
    {
        int v = G[u][i].v;
        if (!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in[v])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u])
    {
        cnt2 ++;
        int node = 0;
        do
        {
            node = s.top();
            s.pop();
            in[node] = false;
            ans[cnt2].push_back(node);
        }while (node != u);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i ++)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back({x, y});
    }
    Tarjan(1);
    for (int i = 1 ; i <= cnt2 ; i ++)
    {
        sort(ans[i].begin(), ans[i].end());
    }
    cout << cnt2 << endl;
    for (int i = cnt / 2 ; i >= 1 ; i --)
    {
        for (int j = 0 ; j < ans[i].size() ; j ++)
        {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

by xfrvq @ 2021-08-09 08:58:32

？您这是是按顺序输出强连通分量，但是题目要求按1号节点，2号节点的顺序输出

by qfpjm @ 2021-08-09 09:08:51

@滑翔翼 我该怎样改？

by xfrvq @ 2021-08-09 09:24:02

@Ted何家乐 给每个强连通分量一个id，记录下每个点对应的强连通分量的id

by qfpjm @ 2021-08-09 09:42:21

@滑翔翼 加了id还是全WA。。。

#include <bits/stdc++.h>

using namespace std;

struct edge
{
    int u, v;
};

int n, m, dfn[100005], low[100005], cnt, cnt2, idx[100005], f[100005];
bool in[100005];
vector<edge> G[100005];
vector<int> ans[100005];
stack<int> s;

void Tarjan(int u)
{
    cnt ++;
    low[u] = cnt;
    dfn[u] = cnt;
    in[u] = true;
    s.push(u);
    for (int i = 0 ; i < G[u].size() ; i ++)
    {
        int v = G[u][i].v;
        if (!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in[v])
        {
            low[u] = min(low[u], low[v]);
        }
    }
    if (dfn[u] == low[u])
    {
        cnt2 ++;
        int node = 0;
        do
        {
            node = s.top();
            s.pop();
            idx[node] = cnt2;
            in[node] = false;
            ans[cnt2].push_back(node);
        }while (node != u);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i ++)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back({x, y});
    }
    Tarjan(1);
    for (int i = 1 ; i <= cnt2 ; i ++)
    {
        sort(ans[i].begin(), ans[i].end());
    }
    cout << cnt2 << endl;
    for (int i = 1 ; i <= n ; i ++)
    {
        if (f[idx[i]])
        {
            continue;
        }
        f[idx[i]] = 1;
        for (int j = 0 ; j < ans[idx[i]].size() ; j ++)
        {
            cout << ans[idx[i]][j] << " ";
        }
        cout << endl;
    }
    return 0;
}