请求加强数据
查看原帖
请求加强数据
174897
zjrdmd楼主2021/2/17 12:32

Rt。如下明显错误的代码可以通过所有数据,模板题有必要重视一下数据强度吧(

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stdlib.h>
#include <stack>
#include <queue>
#define ri register int

inline int read() {
	int x=0,f=1;char 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;
}

void write(int x){
  if(x>9) write(x/10);
  putchar(x%10^48);
}

const int N=1e4+5,M=5e4+5;
int to[M<<1],nxt[M<<1],head[N],cnt=1;
int n,m,ans,tot,dfn[N],low[N];
std::stack<int>st;

void edge_add(int u,int v){
	to[cnt]=v,nxt[cnt]=head[u],head[u]=cnt++;
} 

void dfs(int now){
	dfn[now]=low[now]=++tot;
	st.push(now);
	for(ri i=head[now];i;i=nxt[i]){
		int v=to[i];
		if(!dfn[v])dfs(v),low[now]=std::min(low[now],low[v]);
		else low[now]=std::min(low[now],low[v]);
	}
	if(dfn[now]==low[now]){
		int p=0,sum=0;
		while(p!=now)p=st.top(),st.pop(),sum++;
		if(sum>1)ans++;
	}
}

int main(){
	n=read(),m=read();
	for(ri i=1,u,v;i<=m;u=read(),v=read(),edge_add(u,v),i++);
	for(ri i=1;i<=n;i++){if(!dfn[i])dfs(i);}
	printf("%d",ans); 
	return 0;
}
2021/2/17 12:32
加载中...