网站设计稿尺寸,上海工商局注册公司官网,建网站咨询,浙江振升建设有限公司网站刻录光盘
ssl 2344
题目大意#xff1a;
求连通块
原题#xff1a;
题目描述
在JSOI2005夏令营快要结束的时候#xff0c;很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家#xff0c;以便大家回去后继续学习。组委会觉得这个主意不错#xff01;可是组…刻录光盘
ssl 2344
题目大意
求连通块
原题
题目描述
在JSOI2005夏令营快要结束的时候很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家以便大家回去后继续学习。组委会觉得这个主意不错可是组委会一时没有足够的空光盘没法保证每个人都能拿到刻录上资料的光盘又来不及去买了怎么办呢 组委会把这个难题交给了LHCLHC分析了一下所有营员的地域关系发现有些营员是一个城市的其实他们只需要一张就可以了因为一个人拿到光盘后其他人可以带着U盘之类的东西去拷贝啊 可是LHC调查后发现由于种种原因有些营员并不是那么的合作他们愿意某一些人到他那儿拷贝资料当然也可能不愿意让另外一些人到他那儿拷贝资料这与我们JSOI宣扬的团队合作精神格格不入 现在假设总共有N个营员2N200每个营员的编号为1~N。LHC给每个人发了一张调查表让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然如果A愿意把资料拷贝给B而B又愿意把资料拷贝给C则一旦A获得了资料则BC都会获得资料。 现在请你编写一个程序根据回收上来的调查表帮助LHC计算出组委会至少要刻录多少张光盘才能保证所有营员回去后都能得到夏令营资料
输入输出格式
输入格式
先是一个数N接下来的N行分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第i1行表示第i个营员愿意把资料拷贝给那些营员的编号以一个0结束。如果一个营员不愿意拷贝资料给任何人则相应的行只有1个0一行中的若干数之间用一个空格隔开。
输出格式
一个正整数表示最少要刻录的光盘数。
输入输出样例
输入样例
5
2 3 4 0
4 5 0
0
0
1 0输出样例
1解题思路
用Kosaraju算法先跑一遍Dfs然后按推出顺序反过来跑Dfs跑了几遍就是有几个环要判断有没有到过
代码
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,x,w,num,ans,head[205],v[205],p[205];
struct rec
{int to,next;
}a[40005];
void dfs1(int dep)//第一次
{p[dep]1;//记录for (int ihead[dep];i;ia[i].next)if (!p[a[i].to])dfs1(a[i].to);//Dfsv[num]dep; //记录
}
void dfs2(int dep)
{p[dep]1;for (int ihead[dep];i;ia[i].next)if (!p[a[i].to])dfs2(a[i].to);
}
int main()
{scanf(%d,n);for (int i1;in;i)while (scanf(%d,x),x){a[w].tox;a[w].nexthead[i];head[i]w;}for (int i1;in;i)if (!p[i])dfs1(i);memset(p,0,sizeof(p));for (int in;i0;--i)//按反过来的退出顺序if (!p[v[i]])//到过没{dfs2(v[i]);ans;}printf(%d,ans);
}
