为什么第一个点wa了,其他点全过了,但是自己跑,第一个点也是对的,机子上说我输了0???
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m,x,y,tot,tot_,la[N],la_[N],lnk_[N],lnk[N];
int ne[N],ne_[N],from[N],from_[N],low[N],dfn[N];
int num,top,q[N],sd[N],a[N],du[N],sum[N];
bool vis[N];
int read()
{
int x=0;char c;bool f=false;
c=getchar();if (c=='-') f=1;
while (c<'0'||c>'9') {c=getchar();if (c=='-') f=1;}
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
if (f) x=x*-1;
return x;
}
void add(int x,int y)
{
tot++;ne[tot]=y;from[tot]=x;la[tot]=lnk[x];lnk[x]=tot;
}
void tarjan(int u)
{
low[u]=dfn[u]=++num;
q[++top]=u;vis[u]=1;//入栈
for (int k=lnk[u];k;k=la[k])
{
int v=ne[k];
if (!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (vis[v]) low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u])//找到了
{
int v;
while (u!=v)
{
v=q[top];top--;
sd[v]=u;//哪一块
vis[v]=0;
if (u==v) break;
a[u]+=a[v];
}
}
return;
}
int main()
{
// freopen("1.in","r",stdin);
n=read();m=read();
for (int i=1;i<=m;i++)
{
x=read();y=read();add(x,y);
}
for (int i=1;i<=n;i++)
if (!dfn[i]) tarjan(i);
int ans=0;
for (int i=1;i<=n;i++)
sum[sd[i]]++;
for (int i=1;i<=n;i++)
if (sum[i]>1) ans++;
// if (ans==0) ans=1;
cout<<ans;
return 0;
}
最后那个if加上就对了,WA的数据点数据和样例是一样的
样例输入:
5 4
2 4
3 5
1 2
4 1
样例输出:
1