题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1654
题意：n 个奶牛，m 组互相牵引的关系，从某牛出发的一组牵引关系能回到自身是成功的，问有多数组成功的牵引关系...
尝试将题目说的更人话一点... 结果失败了
裸 tarjan，求缩点后有多少个大小大于等于 2 的点就好....
为什么数组开小会 WA 啊摔，说好的 re 呢... 智障错误调了 10min 代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 100100 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct zgz { int next,to; }edge[N]; int cnt=1,head[N]; void add(int from,int to) { edge[cnt].to=to; edge[cnt].next=head[from]; head[from]=cnt++; } int n,m,y,ans; int dfn[N],low[N],stk[N],vis[N],top,tot,belong[N],scnt; void tarjan(int x) { dfn[x]=low[x]=++tot; vis[x]=1; stk[++top]=x; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(!dfn[to]) { tarjan(to); low[x]=min(low[x],low[to]); } else if(vis[to]) { low[x]=min(low[x],dfn[to]); } } if(low[x]==dfn[x]) { int sz=0; scnt++; do{ y=stk[top--]; sz++; vis[y]=0; }while(x!=y); if(sz>=2)ans++; } } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); add(u,v); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); printf("%d",ans); } |
Comments | NOTHING