P2431(Tarjan)求助,TLE?
  • 板块灌水区
  • 楼主XingnoYi
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/2/25 17:22
  • 上次更新2024/2/25 20:15:13
查看原帖
P2431(Tarjan)求助,TLE?
735797
XingnoYi楼主2024/2/25 17:22

这怎么就 TLE 了?

// P2431
#include <iostream>
#include <stack>
#define big long long
using namespace std;
big n,m,cnt,tot,ans,head[100005];
big dfn[10004],vis[10004],low[10004],inst[10004];
big scc,belong[10004],siz[10004],out[10004]; // scc 编号;属于哪个 scc;该 scc 的大小
stack <big> st;
struct Edge{
    big next,to;
}edge[100005]; // 链式前向星存图
inline big read()
{
    big X=0;
    bool flag=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            flag = 0; 
        }
        ch = getchar();
    }
    while(ch >= '0'&& ch <= '9')
    { 
        X=(X<<1)+(X<<3)+ch-'0';
        ch = getchar();
    }
    if(flag)
    {
        return X;
    }
    return -X;
}
inline void write(big X)
{
    if(X < 0)
    {
        X = -X;
        putchar('-');
    }
    if(X > 9)
    {
        write(X/10);
    }
    putchar(X%10+'0');
}

void add_edge(big u,big v)
{
    edge[++cnt].next = head[u];
    edge[cnt].to = v;
    head[u] = cnt;
}
void tarjan(big u)
{
    dfn[u] = low[u] = ++tot; 
    vis[u] = 1;
    st.push(u), inst[u] = 1;// 初始化
    for(big i = head[u];i != 0;i = edge[i].next) // 继续向下遍历
    {
        big v = edge[i].to;
        if(vis[v] == 0) // 没有访问过该节点
        {
            tarjan(v);
            low[u] = min(low[v],low[u]); // 回溯时的更新
        }
        else if(inst[v]) // 发现一条指向栈内点的边
        {
            low[u] = min(dfn[v],low[u]); // 更新
        }
    }
    if(low[u] == dfn[u]) // 找到一个 scc
    {
        big v; ++scc;
        do
        {
            inst[v=st.top()] = 0; // 取出栈顶元素并维护 inst[] 数组
            st.pop();
            belong[v] = scc;
            siz[scc]++;
        } while(u != v);
    }
}
int main()
{
    n = read(), m = read();
    for(big i = 1;i <= m;i++)
    {
        big u,v;
        u = read(), v = read();
        add_edge(u,v); // 有向边
    }
    for(big i = 1;i <= n;i++) // 保证每个点不遗漏
    {
        if(vis[i] == 0)
        {
            tarjan(i);
        }
    }
    for(big u = 1;u <= n;u++)
    {
        for(big j = head[u];j != 0;j = edge[u].next)
        {
            big v = edge[j].to;
            if(belong[u] != belong[v])
            {
                out[belong[u]]++;
            }
        }
    }
    big count = 0;
    for(big i = 1;i <= scc;i++)
    {
        if(out[i] == 0)
        {
            count++;
            ans += siz[i];
        }
        if(count == 2)
        {
            printf("0");
            return 0;
        }
    }
    write(ans);
    return 0;
}
2024/2/25 17:22
加载中...