社区讨论
样例为什么过不了?tarjan缩点求助
P2746[IOI 1996 / USACO5.3] 校园网 Network of Schools参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @loconwwz
- 此快照首次捕获于
- 2023/10/30 17:14 2 年前
- 此快照最后确认于
- 2023/11/05 04:09 2 年前
如下,
CPPtarjan 模板,样例输出 5 \n 5#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int head[N], cnt = 0;
struct Edge {
int to, next;
} e[N * N];
int n, m, dfn[N], low[N], si[N], co[N], de[N], num = 0, col = 0;
int bok[N][3], in[N], out[N];
inline void add(int u, int v) {
e[++ cnt].to = v;
e[cnt].to = head[u];
head[u] = cnt;
}
int st[N], top = 1;
inline void tarjan(int u) {
dfn[u] = low[u] = ++ num;
st[top ++] = u;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(dfn[v] == 0) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if(co[v] == 0) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
++ col;
while(st[top] != u) {
top --;
co[st[top]] = col;
}
top --;
}
return ;
}
int main() {
scanf("%d", &n);
int k = 0;
for (int a = 1, b; a <= n; ++ a) {
scanf("%d", &b);
while(b != 0) {
add(a, b);
bok[++ k][1] = a;
bok[k][2] = b;
scanf("%d", &b);
}
}
for (int i = 1; i <= n; ++ i) {
if(!dfn[i]) tarjan(i);
}
for (int i = 1; i <= k; ++ i) { // 统计入度和出度
if(co[bok[i][1]] != co[bok[i][2]]) {//同种颜色不需要统计
out[co[bok[i][1]]] ++;
in[co[bok[i][2]]] ++;
}
}
int s1 = 0, s2 = 0;
for (int i = 1; i <= col; ++ i) {
if(in[i] == 0) s1 ++;
if(out[i] == 0) s2 ++;
}
printf("%d\n%d\n", s1, max(s1, s2));
return 0;
}
求助,谢谢了!!!
回复
共 0 条回复,欢迎继续交流。
正在加载回复...