记录编号	454530	评测结果	AAAAAAAAAA
题目名称	网络病毒	最终得分	100
用户昵称	皓芷	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2017-09-29 08:13:21	内存使用	0.40 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<vector>
#include<set>
#define mysister //scc是强连通分量的缩写 
#define maxn 1001
using namespace std;
int n,a,vis[maxn],colour[maxn],cnt=0,ans=0,in[maxn];//定义详见代码 
vector<int>son[maxn];//正图 
vector<int>fa[maxn];//逆图 
vector<int>scc[maxn];//每个scc里的点 
set<int>sccto[maxn];//标号为i的scc所连出去的指向其他scc的边 
vector<int>b[maxn];//新图 
stack<int>sta;//kosaraju第一遍df退出序 
void dfs_1(int u)
{
	vis[u]=1;
	for(int i=0;i<son[u].size();i++)if(!vis[son[u][i]])
	  dfs_1(son[u][i]);
	sta.push(u);
}
void dfs_2(int u)
{
	vis[u]=1;
	colour[u]=cnt;
	scc[cnt].push_back(u);
	for(int i=0;i<fa[u].size();i++)if(!vis[fa[u][i]])
	  dfs_2(fa[u][i]);
}
void inn(int &x)
{
	x=0;int f=1;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9'){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	x*=f;
}
int main()
{
	freopen("virus.in","r",stdin);
	freopen("virus.out","w",stdout);
	inn(n);
	for(int i=0;i<n;i++)
	  for(int j=0;j<n;j++)
	  {
		inn(a);
		if(a)
		{
		  son[i].push_back(j);
		  fa[j].push_back(i);
		}
	  }
	memset(vis,0,sizeof(vis));
	for(int i=0;i<n;i++)
	  if(!vis[i])dfs_1(i);
	memset(vis,0,sizeof(vis));
	while(!sta.empty())
	{
	  if(!vis[sta.top()]){cnt++;dfs_2(sta.top());}
	  sta.pop();
	}
	for(int i=1;i<=cnt;i++)
	  for(int j=0;j<scc[i].size();j++)
	    for(int k=0;k<son[scc[i][j]].size();k++)
		{
		  if(!sccto[i].count(colour[son[scc[i][j]][k]])&&colour[son[scc[i][j]][k]]!=i)
		  {
			b[i].push_back(colour[son[scc[i][j]][k]]);in[colour[son[scc[i][j]][k]]]++;
			sccto[i].insert(colour[son[scc[i][j]][k]]);
		  }
		}
	for(int i=1;i<=cnt;i++)
	  if(!in[i])ans++;
	printf("%d",ans);
	return 0;
}