首页 > > 程序设计 > C/C++ >

【codevs2822】爱在心中

2018-06-17 21:46:39来源：未知阅读 ()

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