2822 爱在心中
**时间限制: 1 s
空间限制: 128000 KB**
传送门
题目等级 : 钻石 Diamond
题目描述 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
分类标签 Tags
SPFA 强连通分量 图论
/*
此题有两个询问：
（1）找连通分量个数（缩点前节点数不唯一的）.
（2）找出度为0且符合（1）的.
Tarjan模板+缩点+统计出度.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 10001
using namespace std;
struct data
{
int v;
int next;
}
e[MAXN];
struct node
{
int l;
int x[1001];
}
g[MAXN];
int dfn[MAXN],low[MAXN],stack[MAXN],n,m,tot,top,cut,ans,b[MAXN],head[MAXN];
bool in[MAXN],s[MAXN];
void add_edge(int u,int v)
{
e[tot].v=v;
e[tot].next=head[u];
head[u]=tot++;
}
void tarjan(int u)
{
int v;
low[u]=dfn[u]=++cut;
in[u]=true;
stack[top++]=u;
for(int i=head[u];i!=-1;i=e[i].next)
{
v=e[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
int l=0,a[MAXN];
tot++,ans++;
g[tot].l=0;
do
{
v=stack[--top];
b[v]=tot;
in[v]=0;
a[++l]=v;
}while(u!=v);
sort(a+1,a+l+1);
g[tot].l=l;
for(int i=1;i<=l;i++)
g[tot].x[i]=a[i];
if(g[tot].l==1) ans--,s[tot]=0;
else s[tot]=1;
}
}
int main()
{
int x,y;
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
add_edge(x,y);
}
tot=0;
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tarjan(i);
}
int out[MAXN]={0};
for(int i=1;i<=n;i++)
{
for(int j=head[i];j!=-1;j=e[j].next)
{
if(b[i]!=b[e[j].v])
out[b[i]]++;
}
}
cout<<ans<<endl;
int xx=-1;
for(int i=1;i<=tot;i++)
{
if(!out[i])
{
if(!s[i]||xx!=-1)
{
xx=-1;
break;
}
else xx=i;
}
}
if(xx==-1) cout<<-1;
else
{
for(int i=1;i<=g[xx].l;i++)
cout<<g[xx].x[i]<<" ";
}
return 0;
}