http://lpoj.cn/problemdetail?problemID=104

tarjan 缩点 求入度为0的联通分量

 

#include<bits/stdc++.h>
#define MAXN 1000010
using namespace std;
int n,a;
int ans,num;
int tnt,head[MAXN],to[MAXN],next1[MAXN];
int low[MAXN];//最早祖先的标号
int mmm[MAXN]; //连通图编号 
int dfn[MAXN]; 
int cnt,vis[MAXN],index1[MAXN];
void add(int a,int b) {
	tnt++; 
	to[tnt]=b;
	next1[tnt]=head[a];
	head[a]=tnt;
	return ;
}
stack<int>s;
void Tarjan(int u) {
	dfn[u]=low[u]=++cnt;
	s.push(u);
	vis[u]=1;
	for(int e=head[u]; e; e=next1[e]) {
		if(!dfn[to[e]]) {
			Tarjan(to[e]);
			low[u]=min(low[u],low[to[e]]); //更新祖先 
		} else if(vis[to[e]]) low[u]=min(low[u],dfn[to[e]]);
	}
	if(low[u]==dfn[u]) {
		num++;
		while(!s.empty() && s.top()!=u)
		{
			mmm[s.top()]=num;
			vis[s.top()]=0;
			s.pop();
		 } 
		if(!s.empty())
		{
			mmm[s.top()]=num;
			vis[s.top()]=0;
			s.pop();
		}
	}
	return ;
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) {
			scanf("%d",&a);
			if(a)
				add(i,j);
		}
	for(int i=1; i<=n; i++)
		if(!dfn[i])
			Tarjan(i);
	for(int u=1; u<=n; u++)
		for(int e=head[u]; e; e=next1[e])
			if(mmm[u]!=mmm[to[e]])
				index1[mmm[to[e]]]++;
	for(int i=1; i<=num; i++)
		if(!index1[i])
			ans++;
	printf("%d\n",ans);
}