记录编号	330840	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]信息传递	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.387 s
提交时间	2016-10-26 21:17:23	内存使用	2.82 MiB

#include "cstdio"
#include "cstring"
#include "algorithm"
#include "stack"
using namespace std;

const int maxnumber = 200100;
struct Edge
{
	int to, next;
}edegs[maxnumber];
int head[maxnumber], tot;
int dfsorder[maxnumber], low[maxnumber], size[maxnumber], sccno[maxnumber], scccnt, dfsclock;
stack <int> S;
int ans = maxnumber;

inline void AddEdge(const int& from, const int& to)
{
	edegs[++tot].to = to;
	edegs[tot].next = head[from];
	head[from] = tot;
}

inline void Read(int& a)
{
	a = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') {
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

void Tarjan(const int& a)
{
	dfsorder[a] = low[a] = ++dfsclock;
	S.push(a);
	for (int i = head[a]; i; i = edegs[i].next) {
		int to = edegs[i].to;
		if (!dfsorder[to]) {
			Tarjan(to);
			low[a] = min(low[a], low[to]);
		}
		else if (!sccno[to]) low[a] = min(low[a], dfsorder[to]);
	}
	if (low[a] == dfsorder[a]) {
		scccnt++;
		while (1) {
			int top = S.top(); S.pop();
			sccno[top] = scccnt;
			size[scccnt]++;
			if (top == a) break;
		}
		if (size[scccnt] > 1) ans = min(ans, size[scccnt]);
	}
}

#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("2015message.in", "r", stdin); freopen("2015message.out", "w", stdout);
#endif

	int __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	int n, to;
	Read(n);
	for (int i = 1; i <= n; ++i) {
		Read(to);
		AddEdge(i, to);
	}
	for (int i = 1; i <= n; ++i)
		if (!sccno[i]) Tarjan(i);
	printf("%d\n", ans);

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}