AC代码

52分WA代码

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef int lsqxx;
struct lq{
	lsqxx v,nxt;
}e[200005];
lsqxx h[20005],cnt;
void add(lsqxx u,lsqxx v)
{
	e[++cnt].v=v;e[cnt].nxt=h[u];h[u]=cnt;
}
int n,m;
int x,y;
int dfn[20005],low[20005],refn[20005];
int vis[20005],dis[20005];
int dfnx;
void tarjan(int t)
{
	dis[t]=1;
	vis[t]=1;
	if(!dfn[t])
		dfn[t]=low[t]=++dfnx,refn[dfnx]=t;
	for(int i=h[t];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(vis[v])
		{
			if(dis[v])
				low[t]=min(low[t],low[v]);
		}
		else
		{
			tarjan(v);
			low[t]=min(low[t],low[v]);
		}
	}
	dis[t]=0;
}
int cnts[20005],ans;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		scanf("%lld%lld",&x,&y),add(x,y);
	for(int i=1;i<=n;i++)
		if(!vis[i])
			tarjan(i);
	for(int i=1;i<=n;i++)
			cnts[refn[low[i]]]++;
	for(int i=1;i<=n;i++)
		if(cnts[i]>1&&low[i]==dfn[i]) ans++;
	cout<<ans;
	return 0;
}

WA代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef int lsqxx;
struct lq{
	lsqxx v,nxt;
}e[200005];
lsqxx h[20005],cnt;
void add(lsqxx u,lsqxx v)
{
	e[++cnt].v=v;e[cnt].nxt=h[u];h[u]=cnt;
}
int n,m;
int x,y;
int dfn[20005],low[20005],refn[20005];
int vis[20005],dis[20005];
int dfnx;
void tarjan(int t)
{
	dis[t]=1;
	vis[t]=1;
	if(!dfn[t])
		dfn[t]=low[t]=++dfnx,refn[dfnx]=t;
	for(int i=h[t];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(vis[v])
		{
			if(dis[v])
				low[t]=min(low[t],low[v]);
		}
		else
		{
			tarjan(v);
			low[t]=min(low[t],low[v]);
		}
	}
	dis[t]=0;
}
int cnts[20005],ans;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		scanf("%lld%lld",&x,&y),add(x,y);
	for(int i=1;i<=n;i++)
		if(!vis[i])
			tarjan(i);
	for(int i=1;i<=n;i++)
			cnts[refn[low[i]]]++;
	for(int i=1;i<=n;i++)
		if(cnts[i]>1/*&&low[i]==dfn[i]*/) ans++;
	cout<<ans;
	return 0;
}

理论上这个 $low[i]==dfn[i]$ 情况没有影响啊