NOIP2015提高组.信息传递

题目

517. 信息传递

算法标签: 并查集, $Tarjan$算法, $scc$强连通分量

思路

使用强连通分量算法求环上点的数量, 对每个连通分量求最小点数

$Tarjan$算法求解代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 200010, M = N;

int n;
int head[N], ed[M], ne[M], idx;
int stk[N], top;
int low[N], dfn[N], timestamp;
int id[N], scc_cnt, cnt[N];
bool in_stk[N];

void add(int u, int v) {
   
	ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void tarjan(int u) {
   
	dfn[u] = low[u] = ++timestamp;
	stk[++top] = u, in_stk[u] = true;

	for (int i = head[u]; ~i; i = ne[i]) {
   
		int v = ed[i];
		if (!dfn[v]) {
   
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
	}

	if (dfn[u] == low[u]) {
   
		++scc_cnt;
		int v;

		do {
   
			v = stk[top--];
			in_stk[v] = false;
			id[v] = scc_cnt;
			cnt[scc_cnt]++;
		}
		while (v != u);
	}
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head,-1, sizeof head);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
   
		int t;
		cin >> t;
		add(i, t);
	}

	for (int i = 1; i <= n; ++i) {
   
		if (!dfn[i]) tarjan(i);
	}

	int ans = n;
	for (int i = 1; i <= scc_cnt; ++i) {
   
		if (cnt[i] > 1) ans = min(ans, cnt[i]);
	}

	cout << ans << "\n";
	return 0;
}