求助 OLE
查看原帖
求助 OLE
366455
西湖水妖楼主2022/7/27 19:10

OLE 应该有人回复吧。

#include <bits/stdc++.h>
using namespace std;
unsigned n, N, u, v, cnt, Time;
array<vector<unsigned>, 4011> e, Scc;
array<unsigned, 4011> dfn, low, scc;
stack<unsigned> st;
char ch;
void read(unsigned &x)
{
    x = 0u;
    do
        ch = getchar();
    while(isspace(ch));
    while(isdigit(ch))
    {
        x *= 10u;
        x += ch;
        x -= '0';
        ch = getchar();
    }
}
void write(const unsigned &x)
{
    if(x > 9u)
        write(x / 10u);
    putchar(x % 10u + '0');
}
void dfs(const unsigned &u)
{
    dfn.at(u) = low.at(u) = ++ Time;
    st.push(u);
    for(const auto &v: e.at(u))
    {
        if(! dfn.at(v))
        {
            dfs(v);
            low.at(u) = min(low.at(u), low.at(v));
        }
        else if(! scc.at(v))
            low.at(u) = min(low.at(u), dfn.at(v));
    }
    if(dfn.at(u) == low.at(u))
    {
        ++ cnt;
        do
        {
            v = st.top();
            st.pop();
            scc.at(v) = cnt;
            if(v >= n)
                Scc.at(cnt).push_back(v - n + 1u);
        } while(u != v);
        sort(Scc.at(cnt).begin(), Scc.at(cnt).end());
    };
}
int main()
{
    while(scanf("%u", &n) != EOF)
    {
        Time = cnt = 0u;
        fill(e.begin() + 1u, e.end(), vector<unsigned>());
        fill(Scc.begin() + 1u, Scc.end(), vector<unsigned>());
        fill(dfn.begin() + 1u, dfn.end(), 0u);
        fill(low.begin() + 1u, low.end(), 0u);
        fill(scc.begin() + 1u, scc.end(), 0u);
        auto E(e.begin() + n + 1);
        for(auto i(e.begin() + 1); i != E; ++ i)
        {
            read(N);
            do
            {
                read(v);
                i -> push_back(v + n);
            } while(-- N);
        }
        for(unsigned i(1u); i != n + 1u; ++ i)
        {
            read(u);
            e.at(u + n).push_back(i);
        }
        ++ n;
        for(unsigned i(1u); i != n; ++ i)
            if(! dfn.at(i))
                dfs(i);
        for(unsigned i(1u); i != n; ++ i)
        {
            write(Scc.at(scc.at(i)).size());
            putchar(' ');
            for(const auto &u: Scc.at(scc.at(i)))
            {
                write(u);
                putchar(' ');
            }
            putchar('\n');
        }
    }
    return 0;
}

2022/7/27 19:10
加载中...