样例为什么过不了?tarjan缩点求助
查看原帖
样例为什么过不了?tarjan缩点求助
213218
蒟蒻CGZ楼主2021/1/30 12:15

如下,tarjan 模板,样例输出 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;
} 

求助,谢谢了!!!

2021/1/30 12:15
加载中...