tarjan+topsort

题目

---

缩完点后统计入读为零的点就可以来。

因为缩完点后肯定是DAG

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int dfn[100100],low[100010],tim;

bool instack[100010];

int stack[100010],top,num;

int belong[100010] ;

struct node

{

	int point;

	int next;

};

node line[100010];

int head[100010],tail;

void add(int x,int y)

{

	line[++tail].point=y;

	line[tail].next=head[x];

	head[x]=tail;

	return ;

}

void tarjan(int x)

{

	dfn[x]=low[x]=++tim;

	stack[++top]=x;

	instack[x]=true;

	int need=head[x];

	while(need)

	{

		if(!dfn[line[need].point])

		{

			tarjan(line[need].point);

			if(low[line[need].point]<low[x])

				low[x]=low[line[need].point];

		}

		else

		if(instack[line[need].point]&&dfn[line[need].point]<low[x])

			low[x]=dfn[line[need].point];

		need=line[need].next;

	}

	if(low[x]==dfn[x])

	{

		num+=1;

		do

		{

			need=stack[top--];

			instack[need]=false;

			belong[need]=num;

		}while(x!=need);

	}

}

int ru[100010];

int main()

{

	int n;

	scanf("%d",&n);

	int a;

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a);

		while(a!=0)

		{

			add(i,a);

			scanf("%d",&a);

		}

	}

	int ans=0;

	for(int i=1;i<=n;i++)

		if(!dfn[i])

			tarjan(i);

	for(int i=1;i<=n;i++)

	{

		int need=head[i];

		while(need)

		{

			if(belong[i]!=belong[line[need].point])

				ru[belong[line[need].point]]+=1;

			need=line[need].next;

		}

	}

	for(int i=1;i<=num;i++)

		if(!ru[i])

			ans+=1;

	printf("%d",ans);

}