本题为什么快读会t11,12,scanf能过
查看原帖
本题为什么快读会t11,12,scanf能过
803851
hualuo_2楼主2024/3/9 09:27

rt,代码如下

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll read()
{
	int f=1,x=0;int ch=getchar();
	while(ch<'0'||ch>'9') if(ch=='-') f=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}

constexpr int mn=1e5+10;
ll dfn[mn],low[mn],tot;
ll stk[mn],instk[mn],top;
ll scc[mn],siz[mn],cnt;
ll n,m,a,b;
vector<int> e[mn];

void tarjan(ll k)
{
	dfn[k]=low[k]=++tot;
	stk[++top]=k;instk[k]=1;
	for(ll y:e[k])
	{
		if(!dfn[y])
		{
			tarjan(y);
			low[k]=min(low[k],low[y]);
		}
		else if(instk[y])
		{
			low[k]=min(low[k],dfn[y]);
		}
	}
	if(dfn[k]==low[k])
	{
		int y;++cnt;
		while(y!=k)
		{
			y=stk[top--];
			instk[y]=0;
			scc[y]=cnt;
			++siz[cnt];		
		}
	}
}

int main()
{
//	n=read();m=read();
	scanf("%lld%lld",&n,&m);
	while(m--)
	{
//		a=read();
//		b=read();
        scanf("%lld%lld",&a,&b);
		e[a].push_back(b);	
	}
	for(int i=1;i<=n;i++)
		{
			if(!dfn[i])
			tarjan(i);
		}
	ll ans=0;
	for(int i=1;i<=cnt;i++)
	{
		if(siz[i]>1) ans++;
	}
	printf("%lld\n",ans);
	return 0;
}
2024/3/9 09:27
加载中...