刻录光盘（Tarjan算法求强连通分量）

本文主要是介绍刻录光盘（Tarjan算法求强连通分量），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目概述
给定N个人和一些人与人之间的关系（u，v），表示u愿意借给v光盘，那么对于存在的（u，v）（v，w）表示u愿意借给v光盘，v愿意借给w光盘，同时u愿意借给w光盘。求最少要用多少光盘才会让这N个人全部能够借到光盘。
数据规模
2<=N<=200
思路
这个题我认为比较难想的就是Tarjan强联通分量缩点，然后变成一个有向无环图，求入度为0的点的个数，然后输出即可。注意这个题存在诡异的读入优化卡时现象，所以还是用scanf输入吧。

#include<iostream>
using namespace std;
int i,j,m,n,temp;
int hd[100001];
int dfn[100001],low[100001];
int col[100001],stack[100001],top,num,colorn;
int b[100001],rd[100001],ttemp;
int array_x[100001],array_y[100001];
struct data
{int y,nxt;
}a[500001];
//int r()
//{
//  int ans=0,f=1;
//  char ch=getchar();
//  while(ch<'0'||ch>'9')
//  {
//      if(ch=='-')
//      f=-1;
//      ch=getchar();
//  }
//  while(ch>='0'&&ch<='9')
//  {
//      ans*=10;
//      ans+=ch-'0';
//      ch=getchar();
//  }
//  return ans*f;
//}inline void add(int xx,int yy)
{a[++temp].y=yy;a[temp].nxt=hd[xx];hd[xx]=temp;
}inline void tarjan(int x)
{dfn[x]=low[x]=++num;b[x]=1;stack[++top]=x;for(int p=hd[x];p;p=a[p].nxt){if(!dfn[a[p].y]){tarjan(a[p].y);low[x]=min(low[x],low[a[p].y]);}else if(b[a[p].y])low[x]=min(low[x],dfn[a[p].y]);}if(dfn[x]==low[x]){b[x]=0;col[x]=++colorn;while(stack[top]!=x){col[stack[top]]=colorn;b[stack[top--]]=0;}top--;}
}int main()
{
//  n=r();scanf("%d",&n);int xx,yy,k;for(i=1;i<=n;i++){array_x[++ttemp]=i,scanf("%d",&array_y[ttemp]);while(array_y[ttemp]){add(i,array_y[ttemp]);array_x[++ttemp]=i,scanf("%d",&array_y[ttemp]);}ttemp--;}for(i=1;i<=n;i++)if(!col[i])tarjan(i);for(i=1;i<=ttemp;i++){if(col[array_x[i]]!=col[array_y[i]])rd[col[array_y[i]]]++;}int ans=0;for(i=1;i<=colorn;i++)if(!rd[i])ans++;cout<<ans;
}
/*
5
2 0
4 3 0
0
3 0
0
*/