这方法是不对的..原因是拓扑排序时有的点的贡献会被多次统计,如1->2 2->3 1->3这个图,设答案点为3,实际上1号点的贡献会被计算两次,因此本题不能直接用拓扑排序来做。然而数据太水因此可以卡过去,但是这是不对滴... 附一个目前数据能过但是不对的代码警醒自己
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200000+15;
int n,m,sum,tim,top,s=0;
int p[maxn],head[maxn],sd[maxn],dfn[maxn],low[maxn];
int stac[maxn];
int h[maxn],in[maxn],dist[maxn];
struct EDGE
{
int to;int next;int from;
}edge[maxn*10],ed[maxn*10];
void add(int x,int y)
{
edge[++sum].next=head[x];
edge[sum].from=x;
edge[sum].to=y;
head[x]=sum;
}
void tarjan(int x)
{
low[x]=dfn[x]=++tim;
stac[++top]=x;in[x]=1;
for (int i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if (!dfn[v]) {
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(in[v])
{
low[x]=min(low[x],dfn[v]);
}
}
if (dfn[x]==low[x])
{
int y;
int cnt=0;
while (y=stac[top--])
{
sd[y]=x;
in[y]=0;
cnt++;
if (x==y) break;
}
p[x]=dist[x]=cnt;
}
}
int topo()
{
queue <int> q;
int tot=0;
for (int i=1;i<=n;i++)
if (sd[i]==i&&!in[i])
{
q.push(i);
}
while (!q.empty())
{
int k=q.front();q.pop();
for (int i=h[k];i;i=ed[i].next)
{
int v=ed[i].to;in[v]--;
p[v]+=p[k];
if (in[v]==0) q.push(v);
}
}
int ans=0;
for (int i=1;i<=n;i++){
if(p[i]>=n&&sd[i]==i){
ans+=dist[i];
}
}
return ans;
}
#define mkp make_pair
map<pair<int,int>,int>mp;
signed main()
{
scanf("%lld%lld",&n,&m);
for (int i=1;i<=m;i++)
{
int u,v;
scanf("%lld%lld",&u,&v);
add(u,v);
}
for (int i=1;i<=n;i++)
if (!dfn[i]) tarjan(i);
int anss=0;
int cnt=0;
for (int i=1;i<=m;i++)
{
int x=sd[edge[i].from],y=sd[edge[i].to];
if (x!=y&&(!mp[mkp(x,y)]))
{
mp[mkp(x,y)]=1;
ed[++s].next=h[x];
ed[s].to=y;
ed[s].from=x;
h[x]=s;
in[y]++;
}
}
printf("%lld",topo());
return 0;
}