【codevs2822】愛在心中

2014年1月26日5580

題目描述?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

代碼

#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <queue> #include <typeinfo> #include <map> #include<bits/stdc++.h> typedef long long ll; using namespace std; #define inf 10000000 inline ll read() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } //***************************************************************struct ss {int u,to,next; } e[50001]; int out[40001]; int head[50001],vis[50001],dfn[50001],low[50001],belong[50001],hav[50001]; int q[50001],inq[50001]; int t=1,bcnt,cnt,n,m,top; void add(int u,int v) {e[t].to=v;e[t].u=u;e[t].next=head[u];head[u]=t++; } void dfs(int u) {vis[u]=inq[u]=1;low[u]=dfn[u]=++cnt;q[++top]=u;for(int i=head[u]; i; i=e[i].next){if(!vis[e[i].to]){dfs(e[i].to);low[u]=min(low[u],low[e[i].to]);}else if(inq[e[i].to])low[u]=min(low[u],dfn[e[i].to]);}int v=-1;if(low[u]==dfn[u]){bcnt++;while(v!=u){v=q[top--];inq[v]=0;belong[v]=bcnt;hav[bcnt]++;}} } void rebuild() {for(int i=1; i<=m; i++){if(belong[e[i].u]!=belong[e[i].to]){out[belong[e[i].u]]++;}} } void tarjan() {for(int i=1; i<=n; i++){if(!vis[i]){dfs(i);}}rebuild(); } void work() {int res=0;int ans;for(int i=1; i<=bcnt; i++){if(out[i]==0){ans=i;res++;}}int bb=0;for(int i=1;i<=bcnt;i++){if(hav[i]>=2)bb++;}cout<<bb<<endl;if(res==1){if(hav[ans]!=1){int kk=0;int hh[50001];for(int i=1; i<=n; i++){if(belong[i]==ans){hh[++kk]=i;}}for(int i=1; i<kk; i++){printf("%d ",hh[i]);}cout<<hh[kk]<<endl;}else cout<<-1<<endl;}else cout<<-1<<endl; } int main() {int u,v;scanf("%d%d",&n,&m);for(int i=1; i<=m; i++){scanf("%d%d",&u,&v);add(u,v);}tarjan();work();return 0; }

?

轉載于:https://www.cnblogs.com/zxhl/p/4730923.html

總結

以上是生活随笔為你收集整理的【codevs2822】爱在心中 tarjan 缩点+理解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。