链式前向星总结

在本质上两种方法一致 何老板： for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); End[i]=y; Next[i]=Last[x]; Last[x]=i; } 函数： inline void add(int x,int y) { edge[++num].to=y; edge[num].next=head[x]; head[x]=num; } 其num可用全局变量代替，则完全一致 int ii; inline void add(int x,int y) { edge[ii].to=y; edge[ii].next=head[x]; head[x]=ii; } int main() { ...... for(ii=1;ii<=m;ii++) { cin>>x>>y; add(x,y); } edge[i].to______End[i] head[x]_______Last[x] edge[i].next_______Next[i] 其遍历相同 for (int i=Last[x];i;i=Next[i]) for(int i=head[x];i;i=edge[i].next)

例题：nkojP4091舞会

 

问题描述

 

     约翰的N(2≤N≤10000)只奶牛非常兴奋，因为这是舞会之夜！她们穿上礼服和新鞋子，别上鲜花，她们要表演圆舞．

    只有奶牛才能表演这种圆舞．圆舞需要一些绳索和一个圆形的水池．奶牛们围在池边站好，顺时针顺序由1到N编号．每只奶牛都面对水池，这样她就能看到其他的每一只奶牛．为了跳这种圆舞，她们找了M(2≤M≤50000)条绳索．若干只奶牛的蹄上握着绳索的一端，绳索沿顺时针方绕过水池，另一端则捆在另一些奶牛身上．这样，一些奶牛就可以牵引另一些奶牛．有的奶牛可能握有很多绳索，也有的奶牛可能一条绳索都没有。      对于一只奶牛，比如说贝茜，她的圆舞跳得是否成功，可以这样检验：沿着她牵引的绳索，按顺时针方向，找到她牵引的奶牛，再沿着这只奶牛牵引的绳索，又找到一只被牵引的奶牛，如此下去，若最终能回到贝茜，则她的圆舞跳得成功，如果这样的检验无法完成，那她的圆舞是不成功的．

     如果两只成功跳圆舞的奶牛有绳索相连，那她们可以同属一个组．

     给出每一条绳索的描述，请找出，成功跳了圆舞的奶牛有多少个组(要求一组至少有两头奶牛)？

输入格式

第1行输入N和M，接下来M行每行两个整数A和B，表示沿顺时针方向A牵引着B.

输出格式

一个整数，表示成功跳圆舞的奶牛组数．

样例输入 1

5 42 43 51 24 1

样例输出 1

1

样例输入 2

9 201 69 63 44 35 66 77 85 19 58 75 99 89 18 11 56 18 51 97 57 6

样例输出 2

2

 

 

正解

求强联通分量

 显然塔尖加链式前项星

要加处理单个强联通分量的情况

#include<bits/stdc++.h> using namespace std; const int maxn=80000+5; struct Node { int to;//边的终点end[] int next; //与该边有相同起点的下一条边的存储位置next[] }; int head[maxn]; //head[i] 表示以i为起点的第一条边（与输入顺序相反）的存储位置，一般初始化为-1 last[] Node edge[maxn]; //int Last[maxn],Next[maxn],End[maxn]; int in[maxn],low[maxn],cnt,scc,num; stack <int> s; bool mark[maxn]; inline void add(int x,int y) { edge[++num].to=y; edge[num].next=head[x]; head[x]=num; } void tarjian(int x) { in[x]=low[x]=++cnt; s.push(x);mark[x]=1; //for (int i=Last[x];i;i=Next[i]) for(int i=head[x];i;i=edge[i].next) //if (!in[End[i]]) if(!in[edge[i].to]) { //tarjian(End[i]); //low[x]=min(low[x],low[End[i]]); tarjian(edge[i].to); low[x]=min(low[x],low[edge[i].to]); } // else if (mark[End[i]]) else if (mark[edge[i].to]) low[x]=min(low[x],low[edge[i].to]); if (low[x]==in[x]) { scc++;int v,count=0; do { v=s.top();s.pop();mark[v]=0; count++; }while (v!=x); if (count==1) scc--; } } int mmain() { int n,m; cin>>n>>m; for ( int i=1;i<=m;i++) { int x,y; cin>>x>>y; add(x,y); //scanf("%d%d",&x,&y); //End[i]=y; //Next[i]=Last[x]; //Last[x]=i; } for (int i=1;i<=n;i++) if (!in[i]) tarjian(i); printf("%d",scc); return 0; } const int main_stack=16; char my_stack[128<<20]; int main(){ __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory"); __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp"); mmain(); __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp"); return 0; }

 

 

 

 

转载于:https://www.cnblogs.com/CXYscxy/p/11018988.html