/*不要说这题多水之类的……我只是想记一下kosaraju这种屌炸天的dfs序延伸算法（说不定能加到我的ygylca里面）*/

题意神马的都不说了，好吧，就是给你个图，n个点，然后n行每行都描述该点的出边，图建完了，然后缩点，然后问多少个点没有入度，再问需要加几条边可以让图变强联通图。

强联通图：图中任意两点之间都能互相到达（前提得是有向图你懂的，无向图就有点乱了，根本不要算法了，暴搜就好了）

强联通分量：同强联通图，不过是图中一部分。

缩点，把一个分量视为一个点，缩起来（一般不缩，都是记录每个点在第几个强联通分量里）

kosaraju算法：这厮乃印度人氏也，算法名之甚屌！算法：正着搜一遍，当出边都跑完时记录其dfn[x]=++cnt;然后反向建图（一般在开始就建好），再根据dfn序n-->1在反向图上跑一遍dfs，能扫到且没被赋值（未分配分量序号）的点都是一个同一个强联通分量里的。

（各种“联通”“连通”我就不管了，别吐槽，好像是连通吧？）

两种代码：

一种是邻接矩阵，就是存个bool map[maxn][maxn]表示能不能通，然后不用建反图。

另一种就是邻接表（链式前向星）了，需要建反图，而且这道题可能是稠密图，所以不建议。

当然，我二分提交了十多遍代码，测出最多有2477条边，用邻接表时可以参考一下。

先不着急贴代码，先写一下我对kosaraju的理解性证明，当然，可能有点不严谨，不乐意看的可以去看这篇博客，写得好像很不错（我是看着有点蒙（没耐心，虽然很短））：

http://blog.csdn.net/dm_vincent/article/details/8554244

好了，说一下我的证明：

先说一下各种变量的含义：

struct KSD
{
int v,next;
}ea[M],eb[M];/*正图，反图*/
int heada[N],headb[N],num,n;/*head数组不说了*/
int dfn[N],cnt;/*dfn可以参照代码*/
int id[N],group;/*id[i]，i在第几个强联通分量里*/
int rd[N],od[N];/*入度出度*/
bool visit[N];/*正图dfs时是否被扫过*/

首先我们在反图上dfs时，扫到即同分量，即在扫i点时，所有能到i点且未赋id的点（包括i点）都是一个强联通分量，我们从这里证起。

若a点和i点强联通，那么可以肯定若b点同样和i点强联通，那么a和b强联通吧？这个很好理解，.水水的.！那么我们只对这个分量里每个点都和i点强联通就好了。

强联通：a能到i，i也能到a。

既然能扫到，那么可以确定a能到i，没异议吧？有异议就想到没异议再往下看。现在我们只需要证明i能到a了！

〇若dfn[a]>dfn[i]，则a肯定有id值了，对吧？那么肯定不能再有i->a了。所以此时我们可以穷举所有的情况。

首先我们dfs时实际上建立了一颗搜索树，我们可以举两种情况，① a在i的子树里。② a不在i的子树里。

先说①。这个i肯定能搜到a没问题吧？（a就是由i搜过去的！）

再说一下②，两种情况：②-①若i在a的子树里，没扫完i给i赋完id值，a是绝对不会赋id值的对吧？那么就矛盾于〇一行了，那么就有②-②i就一定不能在a的子树里面。所以又可以分为两种情况。

②-②-①在他们的lca时，先扫到i分支。②-②-②先扫到a分支。

先说②-②-①：既然扫到了i分支，那么如果i能到a，则因为扫到i时a一定还没被扫过，所以可以从i去扫a，那么就跟前置命题“②-②”矛盾，因为此时a竟然成了i的祖先？！！命题为假。

再说②-②-②：同②-②-①，从i不可以扫到a，否则矛盾于“②”，所以i到不了a。

quit，to②-②（因为两种命题都是false），所以quit，to②，②又是false。

所以可以肯定只有a在i子树里面，才可以使得强联通分量成立！

证毕！

codes：

邻接矩阵：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 105
using namespace std;
//kosaruju算法！ 
int n;
int dfn[N],cnt;
int id[N],group;
int rd[N],od[N];
bool map[N][N],visit[N];

int ans1,ans2;

void init()
{
	cnt=group=0;
	ans1=ans2=0;
	memset(map,0,sizeof(map));
	memset(visit,0,sizeof(visit));
	memset(id,0,sizeof(id));
	memset(rd,0,sizeof(rd));
	memset(od,0,sizeof(od));
}

void dfs(int x)
{
	visit[x]=1;
	for(int i=1;i<=n;i++)if(map[x][i]&&!visit[i])dfs(i);
	dfn[++cnt]=x;
	return ;
}
void dfst(int x)
{
	id[x]=group;
	for(int i=1;i<=n;i++)if(map[i][x]&&!id[i])dfst(i);
	return ;
}

void kosaruju()
{
	int i,j,v;
	for(i=1;i<=n;i++)if(!visit[i])dfs(i);
	for(i=n;i;i--)
	{
		v=dfn[i];
		if(!id[v])
		{
			group++;
			dfst(v);
		}
	}
	return ;
}
void handle()
{
	int i,j,u,v;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			u=id[i];
			v=id[j];
			if(map[i][j]&&u!=v)
			{
				od[u]++;
				rd[v]++;
			}
		}
	}
	for(i=1;i<=group;i++)
	{
		if(!rd[i])ans1++;
		if(!od[i])ans2++;
	}
/*	if(group==1)ans2=0;
	加上这句没有任何用的废话就可以0ms（别忘了删注释）
	我猜可能是编译时发生了某未知影响，并进而影响了评测时间。
	run id：poj 13468874
*/	printf("%d\n",ans1);
	if(group==1)puts("0");
	else printf("%d\n",max(ans1,ans2));
}

int main()
{
//	freopen("test.in","r",stdin);
	int i,a;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(i=1;i<=n;i++)while(scanf("%d",&a),a)map[i][a]=1;
		kosaruju();
		handle();
	}
	return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 105
#define M 2477/*极限数据2477条边，但是正常应该开10010（甚至因为它没说有没有重边，还应该开更大！）*/
using namespace std;
//kosaruju算法！
struct KSD
{
	int v,next;
}ea[M],eb[M];
int heada[N],headb[N],num,n;
int dfn[N],cnt;
int id[N],group;
int rd[N],od[N];
bool visit[N];
int ans1,ans2;

void add(int u,int v)
{
	++num;
	ea[num].v=v;
	eb[num].v=u;
	ea[num].next=heada[u];
	eb[num].next=headb[v];
	heada[u]=headb[v]=num;
}

void init()
{
	ans1=ans2=0;
	num=cnt=group=0;
	memset(id,0,sizeof(id));
	memset(rd,0,sizeof(rd));
	memset(od,0,sizeof(od));
	memset(heada,0,sizeof(heada));
	memset(headb,0,sizeof(headb));
	memset(visit,0,sizeof(visit));
}

void dfs(int x)
{
	int i,v;
	visit[x]=1;
	for(i=heada[x];i;i=ea[i].next)
	{
		v=ea[i].v;
		if(!visit[v])dfs(v);
	}
	dfn[++cnt]=x;
}
void dfst(int x)
{
	int i,v;
	id[x]=group;
	for(i=headb[x];i;i=eb[i].next)
	{
		v=eb[i].v;
		if(!id[v])dfst(v);
	}
}

void kosaruju()
{
	int i,j,v;
	for(i=1;i<=n;i++)if(!visit[i])dfs(i);
	for(i=n;i;i--)
	{
		v=dfn[i];
		if(!id[v])
		{
			group++;
			dfst(v);
		}
	}
	return ;
}
void handle()
{
	int i,j,u,v;
	for(i=1;i<=n;i++)
	{
		u=id[i];
		for(j=heada[i];j;j=ea[j].next)
		{
			v=id[ea[j].v];
			if(u!=v)
			{
				od[u]++;
				rd[v]++;
			}
		}
	}
	for(i=1;i<=group;i++)
	{
		if(!rd[i])ans1++;
		if(!od[i])ans2++;
	}
/*	if(group==1)ans2=0;
	加上这句没有任何用的废话就可以0ms（别忘了删注释）
	我猜可能是编译时发生了某未知影响，并进而影响了评测时间。
	run id：poj 13468874
*/	printf("%d\n",ans1);
	if(group==1)puts("0");
	else printf("%d\n",max(ans1,ans2));
}

int main()
{
//	freopen("test.in","r",stdin);
	int i,a;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(i=1;i<=n;i++)while(scanf("%d",&a),a)add(i,a);
		kosaruju();
		handle();
	}
	return 0;
}

【POJ1236】Network of Schools 强联通分量缩点（本文kosaraju）