求助,92分,wa第一个点,但是自己跑没问题
查看原帖
求助,92分,wa第一个点,但是自己跑没问题
42217
xzjds楼主2023/7/22 10:07

为什么第一个点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

2023/7/22 10:07
加载中...