社区讨论
悬赏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样例错误。
输出了2。
蒟蒻求救。
#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 条回复,欢迎继续交流。
正在加载回复...