codevs2822爱在心中

关键词：

“每个人都拥有一个梦，即使彼此不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，世界就像迷宫，却又让我们此刻相逢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：

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

样例输出1：

2
2 3

样例输出2：

1
-1

【题解】

第一问的答案就是缩点后长度大于1的环的数量。

第二问：注意到一点：缩点后满足条件的点一定是出度为0，那么就好办了，遍历每个点，如果出度为零，记录下来，然后去找。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<algorithm>
 8 using namespace std;
 9 #define MAXN 50010
10 struct node{int y,next;}e[MAXN],e2[MAXN];
11 int n,m,now,len,top,bcnt,Link[MAXN],Link2[MAXN],dfn[MAXN],low[MAXN],instack[MAXN],stack[MAXN],belong[MAXN],size[MAXN];
12 inline int read()
13 {
14     int x=0,f=1;  char ch=getchar();
15     while(!isdigit(ch))  {if(ch==‘-‘)  f=-1;  ch=getchar();}
16     while(isdigit(ch))  {x=x*10+ch-‘0‘;  ch=getchar();}
17     return x*f;
18 }
19 void insert(int x,int y)  {e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
20 void Insert(int x,int y)  {e2[++len].next=Link2[x];Link2[x]=len;e2[len].y=y;}
21 void tarjan(int x)
22 {
23     dfn[x]=low[x]=++now;
24     instack[x]=1;  stack[++top]=x;
25     for(int i=Link[x];i;i=e[i].next)
26     {
27         if(!dfn[e[i].y])
28         {
29             tarjan(e[i].y);
30             low[x]=min(low[x],low[e[i].y]);
31         }
32         else if(instack[e[i].y])  low[x]=min(low[x],dfn[e[i].y]);
33     }
34     if(low[x]==dfn[x])
35     {
36         int y;  bcnt++;
37         do
38         {
39             y=stack[top--];
40             instack[y]=0;
41             belong[y]=bcnt;
42             size[bcnt]++;
43         }while(x!=y);
44     }
45 }
46 int main()
47 {
48     //freopen("cin.in","r",stdin);
49     //freopen("cout.out","w",stdout);
50     n=read();  m=read();
51     for(int i=1;i<=m;i++)
52     {
53         int x=read(),y=read();
54         insert(x,y);
55     }
56     len=0;
57     for(int i=1;i<=n;i++)  if(!dfn[i])  tarjan(i);
58     for(int i=1;i<=n;i++)
59         for(int j=Link[i];j;j=e[j].next)
60             if(belong[e[j].y]!=belong[i])
61                 Insert(belong[i],belong[e[j].y]);
62     int ans=0;
63     for(int i=1;i<=bcnt;i++)
64         if(size[i]>1)  ans++;
65     printf("%d
",ans);
66     ans=-1;
67     for(int i=1;i<=bcnt;i++)
68         if(!Link2[i])
69         {
70             if(ans!=-1||size[i]==1)  {ans=-1;  break;}
71             else ans=i;
72         }
73     if(ans==-1)  {printf("-1
");  return 0;}
74     for(int i=1;i<=n;i++)
75         if(belong[i]==ans)  printf("%d ",i);
76     printf("
");
77     return 0;
78 }

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]爱在心中(代码片段)

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

tarjan笔记1

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

爱在心中

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

vijos——t1626爱在心中

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

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小浣熊松松和朋友到野外露营，没想到遇上了&pi;年一次的大洪水，好在松松是一只爱观察的小浣熊，他发现露营地的地形和洪水有如下性质：①露营地可以被看做是一个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它看起来很糟糕，所以我想确... 查看详情