三沣开发知识 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题
autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml
html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> 【codevs2822】爱在心中 -> 正文阅读
 

[C++]【codevs2822】爱在心中

【codevs2822】爱在心中 题目描述 Description
“每个人都拥有一个梦,即使彼此不相同,能够与你分享,无论失败成功都会感动。爱因为在心中,平凡而不平庸,世界就像迷宫,却又让我们此刻相逢Our Home。”
在爱的国度里有N个人,在他们的心中都有着一个爱的名单,上面记载着他所爱的人(不会出现自爱的情况)。爱是具有传递性的,即如果A爱B,B爱C,则A也爱C。
如果有这样一部分人,他们彼此都相爱,则他们就超越了一切的限制,用集体的爱化身成为一个爱心天使。
现在,我们想知道在这个爱的国度里会出现多少爱心天使。而且,如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的,否则输出-1。
输入描述 Input Description
第1行,两个数N、M,代表爱的国度里有N个人,爱的关系有M条。
第2到第M+1行,每行两个数A、B,代表A爱B。
输出描述 Output Description
第1行,一个数,代表爱的国度里有多少爱心天使。
第2行,如果某个爱心天使被其他所有人和爱心天使所爱则请输出这个爱心天使是由哪些人构成的(从小到大排序),否则输出-1。
样例输入 Sample Input
样例输入1:
6 7
1 2
2 3
3 2
4 2
4 5
5 6
6 4
样例输入2:
3 3
1 2
2 1
2 3
样例输出 Sample Output
样例输出1:
2
2 3
样例输出2:
1
-1
题目意思:
给个图,每个环都算作一个爱心天使(一个点不算环)。第一问求多少个爱心天使,第二问求一个特殊爱心天使(其他任何人都可以将爱传递到这个爱心天使),假如没有就输出-1,反之将这个爱心天使内的人按从小到大输出。
想法(以下的图是引用dalao的,表示感谢):
既然求环,不如用强连通分量?
先求出强连通分量,将同一个环内所有元素缩成一个点(包括一个点的),计算出多少个环(这里不包括一个点的)。
缩点示范图(与题目不违和的图):

第一问就Ok了。
我们可以发现特殊的爱心天使是一个出度为0的缩点。
但并不是出度为0的缩点就是特殊天使下面又有三种情况:
情况①:
出度为0的并不是天使(如3)

情况②:
不只一个出度为0的天使或人(如图中4、1、3)

情况③:只有一个出度为0且为天使(如图中4)

我们需要的是情况③。
那么就在缩完点后,判断是否有多个出度为0,是否特殊天使只有一个元素。
于是乎可以写了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stack>
 6 #define maxn 10005
 7 using namespace std;
 8 int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
12     return x*f;
13 }
14 struct node{int to,next;}e[maxn*2];
15 int n,m,cnt,last[maxn],dfn[maxn],low[maxn],idex=0,Bcnt=0,belong[maxn],instack[maxn],v[maxn],cd[maxn];
16 stack<int> stap;
17 void add(int u,int v){
18     e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
19 }
20 void tarjan(int s){
21     int t;
22     dfn[s]=low[s]=++idex;
23     stap.push(s);instack[s]=1;
24     for(int i=last[s];i;i=e[i].next){
25         t=e[i].to;
26         if(!dfn[t]){
27             tarjan(t);
28             low[s]=min(low[s],low[t]);
29         }
30         else if(instack[t]) low[s]=min(low[s],low[t]);
31     }
32     if(dfn[s]==low[s]){
33         Bcnt++;
34         do{
35             t=stap.top();stap.pop();
36             instack[t]=0;
37             belong[t]=Bcnt;
38             v[Bcnt]++;
39         }while(s!=t);
40     }
41 }
42 int main(){
43     n=read(),m=read();
44     for(int i=1;i<=m;i++){
45         int u=read(),v=read();
46         add(u,v);
47     }
48     for(int i=1;i<=n;i++)  //求连通块 
49         if(!dfn[i])
50             tarjan(i);
51     for(int i=1;i<=n;i++)
52         for(int j=last[i];j;j=e[j].next){  //记录各连通块出度 
53             int v=e[j].to;
54             if(belong[i]!=belong[v])
55                 cd[belong[i]]++;
56         }
57     int ans1=Bcnt,ans2=0,tmp;  //ans1计算爱心天使数,ans2求出度为0且为天使的连通块数量 ,tmp记录出度为0且为天使的连通块编号 
58     for(int i=1;i<=Bcnt;i++)
59         if(cd[i]==0&&v[i]!=1){
60             ans2++;
61             tmp=i;   
62         }
63     for(int i=1;i<=Bcnt;i++)
64         if(v[i]==1)  //排除一个点的连通块 
65             ans1--;
66     printf("%d\n",ans1);
67     if(ans2==1){  //只有一个出度为0且为天使才满足情况 
68         for(int i=1;i<=n;i++)
69             if(tmp==belong[i])
70                 printf("%d ",i);
71     }
72     else printf("-1");
73     return 0;
74 }

  C++ 最新文章
10.21测试
4927 线段树练习5
Eff C++ 笔记1
codevs4919 线段树练习4
洛谷P1720 月落乌啼算钱
POJ 27777 count color (线段树——带lazy
extern "C" 用法解析
Windows 环境搭建cocos2dx 3.x Eclipse的环
设计模式学习笔记
1355: [Baltic2009]Radio Transmission
上一篇文章      下一篇文章      查看所有文章
加:2017-10-11 23:23:59  更:2017-10-11 23:24:10 
 
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2017年10日历
2017-10-22 7:16:08
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库