社区讨论

悬赏1关注! 样例错误输出2。求救。

P2341[USACO03FALL / HAOI2006] 受欢迎的牛 G参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lo3fazwy
此快照首次捕获于
2023/10/24 05:42
2 年前
此快照最后确认于
2023/10/24 05:42
2 年前
查看原帖
悬赏一关注。
样例错误。
输出了2。
蒟蒻求救。
CPP
#include <bits/stdc++.h>
using namespace std;
struct Edge {
	int to, last;
} edge[50005];
int nex[10005], cnt;
int dfn[10005], low[10005], scc[10005], tim, color_cnt, siz[10005];
int du[10005];
int n, m, a, b;
bool in_stack[10005];
stack<int>st;
void add(int x, int y) {
	cnt++;
	edge[cnt].to = y;
	edge[cnt].last = nex[x];
	nex[x] = cnt;
}
void tarjan(int x) {
	dfn[x] = low[x] = ++tim;
	in_stack[x] = 1;
	st.push(x);
	for (int i = nex[x]; i; i = edge[i].last) {
		int v = edge[i].to;
		if (!dfn[v]) {
			tarjan(v);
			low[x] = min(low[x], low[v]);
		} else if (in_stack[v]) {
			low[x] = min(low[x], dfn[v]);
		}
	}
	if (dfn[x] == low[x]) {
		++color_cnt;
		int y;
		do {
			y = st.top();
			st.pop();
			in_stack[y] = false;
			scc[y] = color_cnt;
			siz[color_cnt]++;
		} while (x != y);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b;
		add(a, b);
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= n; i++) {
		for (int j = nex[i]; j; j = edge[j].last) {
			int v = edge[j].to;
			if (scc[i] != scc[v]) {
				du[scc[v]]++;
			}
		}
	}
	int num = 0;
	for (int i = 1; i <= color_cnt; i++) {
		if(!du[i]){
			if(num) {
				cout << 0 << endl;
				return 0; 
			}
			num = i;
		}
	}
	cout << siz[num] << endl;
	return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...