52分mle求调
查看原帖
52分mle求调
638832
XXCCVV楼主2023/6/1 13:22
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>
#pragma comment(linker, "/STACK:10240000000,10240000000")
using namespace std;

struct edge {
	int next,to;
} edges[5000005];

int n,m,cnt,ans;
int head[10005];
int vis[10005],vis_[10005][10005];
int rdu[10005];

void addEdge(int u,int v) {
	edges[++cnt].to=v;
	edges[cnt].next=head[u];
	head[u]=cnt;
}

void add_(int start) {
	queue<pair<int ,int> >que;
	que.push(make_pair(start,start));
	vis[start]=1;
	while(!que.empty()) {
		int now=que.front().second;
		que.pop();
		vis[now]=1;
		for(int i=head[now]; i!=0; i=edges[i].next) {
			int to=edges[i].to;
			if(!vis[to]) {
				vis[to]=1;
				que.push(make_pair(start,to));
			}
			if(!vis_[start][to]) {
				vis_[start][to]=1;
				addEdge(start,to);
			}
		}
	}
}

int main() {
	cin>>n>>m;
	for(int i=1,v,u; i<=m; i++) {
		cin>>u>>v;
		vis_[u][v]=1;
		addEdge(u,v);
	}
	for(int i=1; i<=n; i++) {
		memset(vis,0,sizeof(vis));
		add_(i);
	}
	for(int i=1; i<=n; i++) {
		for(int j=head[i]; j!=0; j=edges[j].next) {
			if(i!=edges[j].to)
				rdu[edges[j].to]++;
		}
	}
	for(int i=1; i<=n; i++) {
		if(rdu[i]>=n-1) {
			ans++;
		}
	}
	cout<<ans;
	return 0;
}
2023/6/1 13:22
加载中...