怀疑打了假的tarjan
查看原帖
怀疑打了假的tarjan
352526
GodStudy楼主2020/11/27 21:27

RTRT 比较震惊,#4-#10TLE????

#include <iostream>

using namespace std;

const int N = 2e2 + 7;

struct Edge {
	int to, next;
}edge[N << 2];

int head[N], cnt;

int dfn[N], low[N], ti;

int stck[N], inst;

int n;

bool flag[N];

int ans, tot;

int belong[N], in[N];//belong属于,就是看看当前节点是否属于同一个强联连通分量
						 //in数组树统计入度 

inline void add(int u, int v) {
	edge[++ cnt].to = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
} 

inline int mina(int a, int b) {
	if (a < b)
		return a;
	return b;
}

void tarjan(int u) {
	dfn[u] = low[u] = ++ ti;
	stck[++ inst] = u;
	flag[u] = 1;
	for (int i = head[u]; ~i; i = edge[i].next) {
		int arrive = edge[i].to;
		if (! dfn[arrive]) {
			tarjan(arrive);
			low[u] = mina(low[u], low[arrive]);
		} else if (flag[arrive]) 
			low[u] = mina(low[u], dfn[arrive]);
	}
	if (dfn[u] == low[u]) {
		int cur;
		tot ++;
		do {
			cur = stck[inst --];
			flag[cur] = 0;
			belong[cur] = tot;//这个点属于当前这个强连通分量内 
		} while(cur != u);
	//	cout << endl; 
	}
	return ;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++)
		head[i] = -1;
	for (int i = 1, people; i <= n; i ++) {
		while(1) {
			cin >> people;
			if (! people)
				break;
			add(i, people);
		}
	}
//	return 0;
	for (int i = 1; i <= n; i ++) {
		if (! dfn[i])
			tarjan(i);
	}
	//cout << tot << endl;
	for (int i = 1; i <= n; i ++) {
		for (int j = head[i]; ~j; j = edge[j].next) {
			int arrive = edge[j].to;
			if (belong[i] != belong[arrive])//若i这个点能到达arrive这个点,因为我们遍历的是i的出边,但是他们不再同一个强连通分量中,就将入度++ 
				in[belong[arrive]] ++;
		}
	} 
	for (int i = 1; i <= tot; i ++) {
		if (! in[i])
			ans ++;//如果有个强连通分量无入度只能加一个光盘 
	}
	cout << ans << endl;
2020/11/27 21:27
加载中...