首页 > 代码库 > Vijos——T1626 爱在心中
Vijos——T1626 爱在心中
https://vijos.org/p/1626
描述
“每个人都拥有一个梦,即使彼此不相同,能够与你分享,无论失败成功都会感动。爱因为在心中,平凡而不平庸,世界就像迷宫,却又让我们此刻相逢Our Home。”
在爱的国度里有N个人,在他们的心中都有着一个爱的名单,上面记载着他所爱的人(不会出现自爱的情况)。爱是具有传递性的,即如果A爱B,B爱C,则A也爱C。
如果有这样一部分人,他们彼此都相爱,则他们就超越了一切的限制,用集体的爱化身成为一个爱心天使。
现在,我们想知道在这个爱的国度里会出现多少爱心天使。而且,如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的,否则输出-1。
格式
输入格式
第1行,两个数N、M,代表爱的国度里有N个人,爱的关系有M条。
第2到第M+1行,每行两个数A、B,代表A爱B。
输出格式
第1行,一个数,代表爱的国度里有多少爱心天使。
第2行,如果某个爱心天使被其他所有人和爱心天使所爱则请输出这个爱心天使是由哪些人构成的(从小到大排序),否则输出-1。
样例1
样例输入1
6 71 22 33 24 24 55 66 4
Copy
样例输出1
22 3
Copy
样例2
样例输入2
3 31 22 12 3
Copy
样例输出2
1-1
Copy
限制
各个测试点1s
提示
对于40%的数据 N<=10 M<=100
对于80%的数据 N<=100 M<=1000
对于100%的数据 N<=1000 M<=10000
来源
Cai0715 原创
NOIP 2009·Dream Team 模拟赛 第一期 第四题
描述里的 “如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的” 的 或 应该是 和
不会自爱->原图里不会有独立点
第一问就是 缩点后新点个数 ,第二问 被所有人爱->出度为0 (要注意新图 出现 爱心天使自爱的情况)~~~
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 const int N(10000*5); 7 int n,m,u,v; 8 9 int head[N],sumedge;10 struct Edge11 {12 int u,v,next;13 Edge(int u=0,int v=0,int next=0):14 u(u),v(v),next(next){}15 }edge[N<<1];16 void ins(int u,int v)17 {18 edge[++sumedge]=Edge(u,v,head[u]);19 head[u]=sumedge;20 }21 22 int dfn[N],low[N],tim;23 int Stack[N],instack[N],top;24 int point[N],col[N],sumcol;25 void DFS(int now)26 {27 low[now]=dfn[now]=++tim;28 Stack[++top]=now;instack[now]=1;29 for(int i=head[now];i;i=edge[i].next)30 {31 int to=edge[i].v;32 if(instack[to]) low[now]=min(low[now],dfn[to]);33 else if(!dfn[to])34 DFS(to),low[now]=min(low[now],low[to]);35 }36 if(low[now]==dfn[now])37 {38 col[now]=++sumcol;39 point[sumcol]++;40 for(;Stack[top]!=now;top--)41 {42 int Top=Stack[top];43 col[Top]=sumcol;44 instack[Top]=0;45 point[sumcol]++;46 }47 instack[now]=0;top--;48 }49 }50 51 int if_,ans,cn,cnt,an[N],s[N],cd[N];52 53 int main()54 {55 scanf("%d%d",&n,&m);56 for(int i=1;i<=m;i++)57 scanf("%d%d",&u,&v),ins(u,v);58 for(int i=1;i<=n;i++)59 if(!dfn[i]) DFS(i);60 for(int i=1;i<=m;i++)61 if(col[edge[i].u]!=col[edge[i].v])62 cd[col[edge[i].u]]++;63 for(int i=1;i<=sumcol;i++)64 {65 if(point[i]>1&&!cd[i]) s[++cn]=i;66 if(point[i]>1) ans++;67 } 68 printf("%d\n",ans);69 if(cn==1)70 {71 for(int i=1;i<=n;i++)72 if(col[i]==s[cn]) an[++cnt]=i;73 sort(an+1,an+cnt+1);74 for(int i=1;i<=cnt;i++)75 printf("%d ",an[i]);76 if_=1;77 }78 if(!if_) printf("-1\n");79 return 0;80 }
Vijos——T1626 爱在心中
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。