首页 > 代码库 > 【强连通分量】10204 - 谁是孽角子

【强连通分量】10204 - 谁是孽角子

2024-07-29 06:30:17   211人阅读

【强连通分量】10204 - 谁是孽角子

Time Limit: 1000MS
Memory Limit: 2048KB

本题由南山卢致远原创！在此感谢！


NSOI 选孽角子了，负责扫地的孽角子，由于大家风度太好，所有都不愿意去争取，经过叶老师的再三思考，决定来一次投票推荐，参加投票的有N个人，将他们按1 — N编号。自己是憋憋推荐自己的、注意，一个人可以投多个人。Nsoi之间的信任存在传递性，如果，A支持B,那么A也会支持B支持的人。如果某个人接获得 所有人的推荐，那么他就有可能是孽角子，这个任务交给了致标，致标抓于马下，所以向你求助，任务统计所有可能是孽角子的人。


输入 ：
 Glover.in
 第一行 N，M  有N个人参加了投票，共投M票。 N<=10000 , M<=40000
 接下来 M 行，每行两个正整数 a , b ; 表示  a 推荐 b;  a <= N && b<= N ;

 输出：
Glover.out
第一行 ：ANS_N  表示有ANS_N个人有机会成为孽角子。
接下来  ANS_N 行， 每行一个数 ，表示有机会成为孽角子人的编号。

 样例 ：
Glover.in
7  10
1 2
2 4
4 3
2 3
3 6
3 5
5 6
6 7
7 5
1 6
Glover.out
3
5
6
7

 1 # include<cstdio> 2 # include<cstring> 3 # include<stack> 4 # include<algorithm> 5 # include<iostream> 6 using namespace std; 7 const int N=30000+10; 8 const int M=60000+10; 9 stack<int>S;10 int n,m,ecnt,scc_cnt,dfs_clock,tot,out_degree,cur;11 int fist[N],next[M],v[M],pre[N],low[N],scc_no[N],size[N],out[N];12 void built(int a,int b){13     ++ecnt;14     v[ecnt]=b;15     next[ecnt]=fist[a];16     fist[a]=ecnt;17 }    18 int check(int a,int b){19     for(int e=fist[a];e!=-1;e=next[e])20     if(v[e]==b)return 0;21     return 1;22 }23 void init(){24     int a,b;25     memset(fist,-1,sizeof(fist));26     scanf("%d%d",&n,&m);27     for(int i=1;i<=m;i++){28         scanf("%d%d",&a,&b);29         if(check(a,b))30         built(a,b);31     }32 }33 int dfs(int u){34     int lowu=pre[u]=++dfs_clock;35     S.push(u);36     for(int e=fist[u];e!=-1;e=next[e])37     if(!pre[v[e]])38     lowu=min(lowu,dfs(v[e]));39     else if(!scc_no[v[e]])40     lowu=min(lowu,pre[v[e]]);41     low[u]=lowu;42     if(low[u]==pre[u]){43         scc_cnt++;44         for(;;){45             int x=S.top();S.pop();46             scc_no[x]=scc_cnt;47             if(x==u)break;48         }49     }50     return low[u];51 }52 void find_scc(){53     memset(pre,0,sizeof(pre));54     memset(low,0,sizeof(low));55     for(int i=1;i<=n;i++)56     if(!pre[i])dfs(i);57 }58 void work(){59     for(int i=1;i<=n;i++)for(int e=fist[i];e!=-1;e=next[e])60     if(scc_no[i]!=scc_no[v[e]])out[scc_no[i]]++;61     for(int i=1;i<=scc_cnt;i++)if(out[i]==0){out_degree=i;cur++;}62     if(cur!=1){printf("0");return;} 63     for(int i=1;i<=n;i++)if(scc_no[i]==out_degree)tot++;64     printf("%d\n",tot);65     for(int i=1;i<=n;i++)if(scc_no[i]==out_degree)printf("%d\n",i);66 }67 int main(){68     init();69     find_scc();70     work();71     return 0;72 }

 

【强连通分量】10204 - 谁是孽角子


联系
我们