又WA又RE求条

B3609 [图论与代数结构 701] 强连通分量

__dragon_ @ 2024-11-14 18:45:49

#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 10000;
struct edge{
    int v,nxt;
}e[maxn * 20];
int n,m;
int head[maxn],idx;
int low[maxn],dfn[maxn],cnt;
int bel[maxn];
bool vis[maxn];
int sc;
vector<int>scc[maxn];
stack<int>st;
void adde(int u,int v)
{
    ++idx;
    e[idx].v = v;
    e[idx].nxt = head[u];
    head[u] = idx;
}
void tarjan(int u)
{
    low[u] = dfn[u] = ++cnt;
    vis[u] = 1;
    st.push(u);
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if (vis[v])
            low[u] = min(low[u],dfn[v]);
    }
    if (low[u] == dfn[u])
    {
        sc ++;
        while (st.top() != u)
        {
            scc[sc].push_back(st.top());
            bel[st.top()] = sc;
            vis[st.top()] = 0;
            st.pop();
        }
        scc[sc].push_back(u);
        bel[u] = sc;
        vis[u] = 0;
        st.pop();
    }
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    while (m--)
    {
        int u,v;
        scanf("%lld%lld",&u,&v);
        if(u == v)
            continue;
        adde(u,v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    printf("%lld\n",sc);
    for (int i = 1; i <= sc; i++)
        sort(scc[i].begin(),scc[i].end());
    bool b[maxn] = {};
    for (int i = 1; i <= n; i++)
    {
        if (!b[bel[i]])
        {
            for (auto j : scc[bel[i]])
                printf("%lld ",j);
            putchar('\n');
            b[bel[i]] = 1;
        }
    }
    return 0;
}

by __dragon_ @ 2024-11-14 18:49:32

死因:数组没开够

此贴结


|