noip2015day1t2

tarjan跑一遍然后找大于1最小的联通分量

#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int maxn=200000+10;
struct hh
{
  int u,v,nex;
}a[maxn];
int n,ord,tot,top,point,ans=2147483647;
int hea[maxn],dfn[maxn],low[maxn],vis[maxn],stack[maxn],belong[maxn],size[maxn];
template <class T> void read(T&x)
{
  x=0;char c=getchar();int f=0;
  while(c<'0'||c>'9'){f|=(c=='-');c=getchar();}
  while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
  x=f?-x:x;
}
void tarjan(int x)
{
  vis[x]=1;
  low[x]=dfn[x]=++ord;
  stack[++top]=x;
  for(register int i=hea[x];i!=-1;i=a[i].nex)
  {
    int v=a[i].v;
    if(!dfn[v])tarjan(v);
    if(vis[v])low[x]=min(low[x],low[v]);
  }
  if(low[x]==dfn[x])
  {
      tot++;int v;
      do
      {
        v=stack[top--];
      vis[v]=0;
      belong[v]=tot;
      size[tot]++;    
    }while(v!=x);
  }
}
void add(int u,int v){a[++point].u=u;a[point].v=v;a[point].nex=hea[u];hea[u]=point;}
int main()
{
  memset(hea,-1,sizeof(hea));
  read(n);
  int v;
  for(register int i=1;i<=n;i++)
  {
      read(v);
      add(i,v);
  }
  for(register int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
  for(register int i=1;i<=tot;i++)if(size[i]>1)ans=min(ans,size[i]);
  printf("%d
",ans);
  return 0;
}