正文

codevs2822爱在心中

Emine  Emine  2022-09-22  683

关键词：

题目描述 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
",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 }

codevs2822爱在心中

...不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，世界就像迷宫，却又让我们此刻相逢OurHome。”在爱的国度里有N个人，在他们的心中都有着一个爱的名单，上面记载着他所爱的人（不会出现自... 查看详情

codevs2822爱在心中tarjan（强联通分量）

2822爱在心中时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond 题目描述 Description“每个人都拥有一个梦，即使彼此不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，... 查看详情

[codevs2822]爱在心中

思路：Tarjan+缩点。首先跑一遍Tarjan，统计结点个数大于$1$的连通分量个数。然后寻找统计结点个数大于$1$且出度为$0$的连通分量，若只存在一个这样的连通分量，输出其点集即可。1#include<stack>2#include<cstdio>3#include<ccty... 查看详情

强连通分量——爱在心中(codevs_2822)——tarjan求scc

scc找只有一个节点的强连通分量，标记。第一行输出强连通分量个数（不为1个节点）缩点建图找出度为0的点。超过一个或者该点被标记，puts（“-1”）；else输出答案。#include<iostream>#include<cstdio>#include<vector>#include&l... 查看详情

codves2822爱在心中

　　　　　　　　　　　　2822爱在心中时间限制:1s 空间限制:128000KB 题目描述 Description“每个人都拥有一个梦，即使彼此不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，... 查看详情

[codevs2882]爱在心中(代码片段)

tarjan笔记1

Tarjan2822爱在心中**时间限制:1s**空间限制:128000KB**题目等级:钻石Diamond题解题目描述Description“每个人都拥有一个梦，即使彼此不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，世界就像迷宫，却又... 查看详情

爱在心中

爱在心中 vijos-1626jdoj-1588　　　　题目大意：给你n个点和m条有向边，求出大于一的强连通分量的个数以及是否存在唯一的强连通分量使得这个分量可以被任意点到达。如果存在，则排序输出这个强联通分量里的点，如果不存... 查看详情

vijos——t1626爱在心中

codevs2822

解题思路：tarjan缩点后算出度为0的点有几个，如果只有一个且这个点为爱心天使就行了；#include<iostream>#include<algorithm>#include<vector>#include<queue>#include<cstdio>#include<cstring>#definemaxn10005usi 查看详情

codevs3165爱改名的小融2

3149爱改名的小融2http://codevs.cn/problem/3149/题目描述 DescriptionWikioi上有个人叫小融，他喜欢改名。现在他的要求变了，只要是英文字母就是他的名字。先给你N个名字，请你一一判断是不是小融。本题还加强了测试数据输入... 查看详情

ac日记——爱改名的小融codevs2967

2967爱改名的小融时间限制:1s 空间限制:16000KB 题目等级:白银Silver题解题目描述 DescriptionWikioi上有个人叫小融，他喜欢改名。他的名字都是英文，只要按顺序出现R,K,Y三个字母，就是他的名字。给... 查看详情

ac日记——爱改名的小融3codevs3156

3156爱改名的小融3 时间限制:1s 空间限制:128000KB 题目等级:黄金Gold题解题目描述 DescriptionWikioi上有个人叫小融，他喜欢改名。现在他的要求变了，只要是英文字母就是他的名字。先给你N个名字，... 查看详情

ac日记——爱改名的小融2codevs3149

3149爱改名的小融2 时间限制:2s 空间限制:128000KB 题目等级:黄金Gold题解题目描述 DescriptionWikioi上有个人叫小融，他喜欢改名。现在他的要求变了，只要是英文字母就是他的名字。先给你N个名字，... 查看详情

受欢迎的牛

...想法：这题也是一道tarjan裸题，让我来A掉吧！这题和爱在心中(爱在心中？猛戳)类似，只不过这题有坑......用panxf的模板A不掉这道题......为什么呢？因为n的数据范围，会MLE。但是我们发现，这道查看详情

codevs3411洪水

题目描述 Description小浣熊松松和朋友到野外露营，没想到遇上了π年一次的大洪水，好在松松是一只爱观察的小浣熊，他发现露营地的地形和洪水有如下性质：①露营地可以被看做是一个N*M的矩形方阵，其中左上角坐标... 查看详情

codevs2277爱吃皮蛋的小明

时间限制:1s 空间限制:32000KB 题目等级:白银Silver题目描述 Description小明特别爱吃蛋，特别是皮蛋。他一次可以吃一个蛋或者两个蛋（整个吞下去），而且他喜欢吃得有花样，他想知道对于一定蛋的数量，有几种不同的... 查看详情

在 JAVA 中解析 RFC 2822 日期

】在JAVA中解析RFC2822日期【英文标题】：ParsingRFC2822dateinJAVA【发布时间】：2011-01-2808:21:20【问题描述】：我需要在Java中解析日期的RFC2822字符串表示。示例字符串在这里：2010年3月13日星期六11:29:05-0800它看起来很糟糕，所以我想确... 查看详情