这怎么就 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;
}