首页 > 代码库 > Vijos Victoria的舞会3
Vijos Victoria的舞会3
描述
Victoria是一位颇有成就的艺术家，他因油画作品《我爱北京天安门》闻名于世界。现在，他为了报答帮助他的同行们，准备开一个舞会。
Victoria准备邀请n个已经确定的人，可是问题来了：
这n个人每一个人都有一个小花名册，名册里面写着他能够通知到的人的名字。比如说在A的人名单里写了B，那么表示A能够通知到B；但是B的名单里不见的有A，也就是说B不见得通知到A。
Victoria觉得需要确定自己需要通知多少个人m，能够实际将所有人n都通知到。并求出一种方案以确定m的最小值是多少。
注意：自己的名单里面不会有自己的名字。Victoria可以自身通知到所有n个人。
格式
输入格式
第一行一个数n。接下来n行，每i+1行表示编号为i的人的小花名册名单，名单以0结束。\
1<=n<=200。
输出格式
一个数，m。
样例1
样例输入1
18011 000016 014 00002 13 0011 07 006 000Copy
样例输出1
14Copy
限制
各个测试点1s
1 /* 2 一个tarjan裸题 3 不过不能只求强连通分量的个数 4 如果有 A 可以通知 B 而 B 无法通知 A 5 那么ans就会加两次 6 只需要建新图 统计出入度就好了 7 */ 8 #include<cstdio> 9 #include<iostream>10 #define MAXN 100011 12 using namespace std;13 14 int n,in[MAXN],ans;15 16 int dfn[MAXN],low[MAXN],stack[MAXN],belong[MAXN],inr,cnt,top;17 bool vis[MAXN];18 19 struct node {20 int to;21 int next;22 };23 node e[MAXN*10];24 25 int head[MAXN],tot;26 27 inline void read(int&x) {28 x=0;int f=1;char c=getchar();29 while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();}30 while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();}31 x=x*f;32 }33 34 inline void add(int x,int y) {35 e[++tot].to=y;36 e[tot].next=head[x];37 head[x]=tot;38 }39 40 inline void tarjan(int u) {41 dfn[u]=low[u]=++inr;42 vis[u]=true;43 stack[++top]=u;44 for(int i=head[u];i;i=e[i].next) {45 int v=e[i].to;46 if(!dfn[v]) {47 tarjan(v);48 low[u]=min(low[u],low[v]);49 }50 else if(vis[v]) low[u]=min(low[u],dfn[v]);51 }52 if(dfn[u]==low[u]) {53 ++cnt;54 int t;55 do {56 t=stack[top--];57 vis[t]=false;58 belong[t]=cnt;59 }while(u!=t);60 }61 }62 63 int main() {64 int x;65 read(n);66 for(int i=1;i<=n;i++) {67 while(1) {68 read(x);69 if(!x) break;70 else add(i,x);71 }72 }73 for(int i=1;i<=n;i++) 74 if(!dfn[i])75 tarjan(i);76 for(int i=1;i<=n;i++) 77 for(int j=head[i];j;j=e[j].next) {78 int v=e[j].to;79 if(belong[i]!=belong[v])80 in[belong[v]]++;81 }82 for(int i=1;i<=cnt;i++)83 if(in[i]==0) ans++;84 printf("%d\n",ans);85 return 0;86 }
Vijos Victoria的舞会3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。