P1726 上白泽慧音:
题目描述:
输入格式:
输出格式:
输入输出样例:
输入 #1
5 5 1 2 1 1 3 2 2 4 2 5 1 2 3 5 1
输出 #1
3 1 3 5
说明/提示:
分析:
简单缩点......实在是没啥可写的。put code
Code:
#include<bits/stdc++.h> using namespace std; const int N=5e4+10; int n,m; int x,y; int sum[N],head[N],low[N],dfn[N],g[N]; int top,cnt,tot,sta[N],Time; bool vis[N]; struct edge{ int to; int ne; }e[N]; void add(int u,int v){ e[++cnt].to=v; e[cnt].ne=head[u]; head[u]=cnt; } void tarjan(int u){ dfn[u]=low[u]=++Time; vis[u]=1;sta[++top]=u; for(int i=head[u];i;i=e[i].ne){ int v = e[i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } if(vis[v]){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ tot++; while(sta[top+1]!=u){ int v = sta[top--]; sum[tot]++; g[v]=tot; vis[v]=0; } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); add(x,y); } for(int i=1;i<=n;i++){ if(!dfn[i])tarjan(i); } int ans=0; for(int i=1;i<=tot;i++){ if(sum[i]>1)ans++; } printf("%d\n",ans); return 0; }
OVER
点关注不迷路,点推荐不妄心