72pts求助!
查看原帖
72pts求助!
678447
CSPAK_Zhangxiuqi0011楼主2024/8/5 19:52

WA的点全都是我的代码输出0,不知道哪里错了,求调!

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>ve[10005],num[10005];
stack<int>stk;
int visit[10005],rk[10005],mn[10005],number,isout[10005],v[10005];
int n,m;
void dfs1(int now) {
	rk[now] = ++number;
	mn[now] = number;
	stk.push(now);
	visit[now] = 1;
	int l;
	l = ve[now].size();
	for(int i = 0; i<l; i++) {
		if(!rk[ve[now][i]]) {
			dfs1(ve[now][i]);
			mn[now] = min(mn[now],mn[ve[now][i]]);
		} else if(visit[ve[now][i]]) {
			mn[now] = min(mn[now],rk[ve[now][i]]);
		}
	}
	if(rk[now] == mn[now]) {
		m++;
		while(now!=stk.top()) {
			num[m].push_back(stk.top());
			visit[stk.top()] = 0;
			stk.pop();
		}
		num[m].push_back(stk.top());
		visit[stk.top()] = 0;
		stk.pop();
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	while(m--) {
		int u,v;
		cin>>u>>v;
		ve[u].push_back(v);
	}
	m++;
	for(int i = 1; i<=n; i++) {
		if(!rk[i]) {
			dfs1(i);
		}
	}
	for(int i = 1; i<=n; i++) {
		int l;
		l = ve[i].size();
		for(int j = 0; j<l; j++) {
			if(mn[i]!=mn[ve[i][j]]) {
				isout[mn[i]] = 1;
			}
		}
	}
	int ans,w;
	ans = 0;
	for(int i = 1; i<=m; i++) {
		if(!isout[mn[num[i][0]]]) {
			ans++;
			w = i;
		}
	}
	cout<<(ans == 1?num[w].size():0)<<"\n";
	return 0;
}
2024/8/5 19:52
加载中...