刻录光盘

题目链接

题目分析

裸的缩点，不理解请学习完缩点再做这题。QAQ

代码

#include<iostream>
#include<vector>
using namespace std;
const int maxn=1e6+7;
//链式前向星
struct Edge
{
	int v, next;
} E[4 * maxn];
int Head[maxn], num_edge;
void Add(int u, int v)
{
	E[++num_edge].next=Head[u];
	E[num_edge].v=v;
	Head[u]=num_edge;
}
//缩点
vector <int> S;
int DFN[maxn],LOW[maxn],idx[maxn];
bool vis[maxn],cd[maxn];
int N,cnt,num;//cnt代表强连通分量个数,num表示DFN顺序
void Tarjan(int x)//求缩点
{
	DFN[x]=LOW[x]=++num;
	S.push_back(x);
	vis[x]=true;
	for(int i=Head[x]; i; i=E[i].next)
	{
		int v=E[i].v;
		if(DFN[v]==0)//未搜索过
		{
			Tarjan(v);
			LOW[x]=min(LOW[x],LOW[v]);
		}
		else if(vis[v])//节点v在栈中
		{
			LOW[x]=min(LOW[x],LOW[v]);
		}
	}
	if(LOW[x]==DFN[x])
	{
		++cnt;
		while(S.back()!=x)
		{

			vis[S.back()]=false;//出栈
			idx[S.back()]=cnt;
			S.pop_back();
		}
		vis[S.back()]=false;//出栈
		idx[S.back()]=cnt;
		S.pop_back();
	}
}
int main()
{
	cin >> N;
	for (int i = 1; i <= N; ++i)
	{
		int v;
		while (1)
		{
			cin >> v;
			if (v == 0) break;
			Add(i, v);
		}
	}
	for(int i=1; i<=N; ++i)//需要对每个点求强连通分量，当然已经搜索过的点就不用了
	{
		if(DFN[i]) continue;
		Tarjan(i);
	}
	for(int i=1; i<=cnt; ++i) cd[i]=true; //表示第i组强连通分量需要光盘
	for(int u=1; u<=N; ++u)
	{
		for(int i=Head[u]; i; i=E[i].next)
		{
			int v=E[i].v;
			if(idx[v]!=idx[u]) cd[idx[v]]=false;//idx[u]能给idx[v]光盘，所以idx[v]不需要光盘了
			}
	}
	int ans=0;
	for(int i=1; i<=cnt; ++i) if(cd[i]) ans++; //统计需要的光盘数量
	cout<<ans;


}