1 条题解
-
0赵青海 (huhe) LV 7 SU @ 2021-8-8 10:44:35
C++ :
#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<queue> #include<stack> #include<cmath> #include<set> #include<map> #include<functional> using namespace std; #define ll long long typedef pair<ll,int>P; const ll INF=1e17+10; const int N=105,mod=1e9+7; struct A{ int to,nex; }edge[N*N]; int n; int head[N],cnt=0,tot=0,vis[N],number; int dfn[N],low[N],sta[N],inx=0,fa[N]; int in[N],out[N]; void add(int from,int to){ edge[cnt].to=to; edge[cnt].nex=head[from]; head[from]=cnt++; } void tarjan(int x){ dfn[x]=low[x]=++tot; sta[++inx]=x; vis[x]=1; for(int i=head[x];i!=-1;i=edge[i].nex){ int v=edge[i].to; if(!dfn[v]){ tarjan(v); low[x]=min(low[x],low[v]); } else if(vis[v]){ low[x]=min(low[x],dfn[v]); } } if(low[x]==dfn[x]){ do{ int t=sta[inx--]; fa[t]=number; vis[t]=0; }while(x!=sta[inx+1]); number++; } } void rebuild(){ for(int i=1;i<=n;i++){ for(int j=head[i];j!=-1;j=edge[j].nex){ int v=edge[j].to; if(fa[i]!=fa[v]){ in[fa[v]]++; out[fa[i]]++; } } } } int main(){ int t; scanf("%d",&n); memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++){ while(scanf("%d",&t)&&t){ add(i,t); } } for(int i=1;i<=n;i++){ if(!dfn[i]){ tarjan(i); } } rebuild(); int ru=0,chu=0; for(int i=0;i<number;i++){ if(!in[i])ru++; if(!out[i])chu++; } if(number==1){ printf("1\n0\n"); } else{ printf("%d\n%d\n",ru,max(ru,chu)); } }
- 1
信息
- ID
- 277
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 8
- 已通过
- 7
- 上传者