[강 연통 분량] vijos 1626 사랑 은 마음속 에 있어 요.

묘사 하 다.
"누구나 하나의 꿈 을 가지 고 있 습 니 다. 서로 다 르 더 라 도 당신 과 나 눌 수 있 습 니 다. 실패 와 성공 에 도 감동 합 니 다. 사랑 은 마음 속 에 있 기 때문에 평범 하지 않 고 평범 하지 않 습 니 다. 세상 은 미로 와 같 지만 지금 우 리 를 만 나 게 합 니 다 Our Home."
사랑 의 나라 에는 N 명 이 있 고, 그들의 마음속 에는 사랑 의 명단 이 있 으 며, 그 위 에 그 가 사랑 하 는 사람 이 기록 되 어 있다.사랑 은 전달 적 인 것 이다. 즉, A 가 B 를 사랑 하고 B 가 C 를 사랑한다 면 A 도 C 를 사랑한다.
이런 일부 사람들 이 서로 사랑한다 면 그들 은 모든 제한 을 넘 어 집단의 사랑 으로 사랑 의 천사 로 변신 할 것 이다.
지금 우 리 는 이 사랑 의 나라 에 얼마나 많은 사랑 의 천사 가 나타 날 지 알 고 싶다.그리고 어떤 사랑 의 천사 가 다른 모든 사람 이나 사랑 의 천사 에 게 사랑 을 받는다 면 이 사랑 의 천사 가 어떤 사람 으로 구성 되 어 있 는 지 출력 하 세 요. 그렇지 않 으 면 출력 - 1.
격식.
입력 형식
첫 번 째 줄 은 두 개의 N, M 으로 사랑 의 나 라 를 대표 하 는 N 사람 이 있 고 사랑 의 관 계 는 M 조 가 있다.
두 번 째 부터 M + 1 줄 까지 줄 마다 두 개의 A, B 를 세 는 것 은 A 애 B 를 대표 한다.
출력 형식
첫 번 째 줄 은 사랑 의 나라 에 사랑 의 천사 가 얼마나 있 는 지 세 어 보 세 요.
두 번 째 줄, 만약 에 어떤 사랑 의 천사 가 다른 모든 사람과 사랑 의 천사 에 게 사랑 을 받는다 면 이 사랑 의 천사 가 어떤 사람 으로 구성 되 어 있 는 지 출력 하 십시오 (어 릴 때 부터 정렬). 그렇지 않 으 면 출력 - 1.
샘플 1
샘플 입력 1 [복사]

6 7

1 2

2 3

3 2

4 2

4 5

5 6

6 4

샘플 출력 1 [복사]

2

2 3

샘플 2
샘플 입력 2 [복사]

3 3

1 2

2 1

2 3

샘플 출력 2 [복사]

1

-1

제한 하 다.
각 테스트 포인트 1s
제시 하 다.
40% 의 데이터 에 대해 N < = 10 M < = 100 대 80% 의 데이터 N < = 100 M < = 1000 대 100% 의 데이터 N < = 1000 M < = 10000
근원
Cai 0715 오리지널 NOIP 2009 · 드 림 팀 시 뮬 레이 션 1 기 4 번
강 연통 분량 + 축 점
축 소 된 그림 은 유 향 무 환 도 이기 때문이다.
그래서 항상 출 도 (out degree) 가 0 인 연결 분량 이 있 습 니 다.
출도 가 0 인 점 이 하나 밖 에 없다 면
모든 연결 분량 이 그 를 가리 키 고 있다 는 것 을 증명 하기 어렵 지 않다.
PS:
1. 이 문 제 는 한 사람의 연결 분량 만 사랑 의 천사 가 아니다.
2. 점 을 줄 인 후에 출 도 0 의 점 을 찾 으 면 개 수가 1 개 이상 인 것 을 - 1 로 판단 해 야 한다.
셋: 하나 뿐 이 고 이 점 이 혼자 가 아니라면

# include<cstdio> # include<cstring> # include<stack> # include<algorithm> # include<iostream>

using namespace std; const int N=1000+10; const int M=10000+10; stack<int>S; int n,m,ecnt,scc_cnt,dfs_clock,tot,out_degree,cur; int fist[N],next[M],v[M],pre[N],low[N],scc_no[N],size[N],out[N]; void built(int a,int b){ ++ecnt; v[ecnt]=b; next[ecnt]=fist[a]; fist[a]=ecnt; } void init(){ int a,b; memset(fist,-1,sizeof(fist)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&a,&b); built(a,b); } } int dfs(int u){ int lowu=pre[u]=++dfs_clock; S.push(u); for(int e=fist[u];e!=-1;e=next[e]) if(!pre[v[e]]) lowu=min(lowu,dfs(v[e])); else if(!scc_no[v[e]]) lowu=min(lowu,pre[v[e]]); low[u]=lowu; if(low[u]==pre[u]){ scc_cnt++; for(;;){ int x=S.top();S.pop(); scc_no[x]=scc_cnt; if(x==u)break; } } return low[u]; } void find_scc(){ memset(pre,0,sizeof(pre)); memset(low,0,sizeof(low)); for(int i=1;i<=n;i++) if(!pre[i])dfs(i); } void work(){ for(int i=1;i<=n;i++)size[scc_no[i]]++; for(int i=1;i<=scc_cnt;i++)if(size[i]>1)tot++; printf("%d
",tot); for(int i=1;i<=n;i++)for(int e=fist[i];e!=-1;e=next[e]) if(scc_no[i]!=scc_no[v[e]])out[scc_no[i]]++;//  scc_no          

    for(int i=1;i<=scc_cnt;i++)if(out[i]==0){out_degree=i;cur++;} if(cur>1||size[out_degree]==1){printf("-1");return;} for(int i=1;i<=n;i++)if(scc_no[i]==out_degree)printf("%d ",i); } int main(){ init(); find_scc(); work(); return 0; }