-【精品资料】ACM大赛必备_常用函数整理_ACM模板(整理版)

并查集void UFset( ) //初始化{for( int i=0; i<N; i++ )parent[i] = -1;}int Find( int x ) //查找并返回结点x所属集合的根结点{int s; //查找位置//一直查找到parent[s]为负数(此时的s即为根结点)为止for( s=x; parent[s]>=0; s=parent[s] );while( s!=x ) //优化方案―压缩路径，使后续的查找操作加速{int tmp = parent[x];parent[x] = s;x = tmp;}return s;}//R1和R2是两个元素，属于两个不同的集合，现在合并这两个集合void Union( int R1, int R2 ){//r1为R1的根结点，r2为R2的根结点int r1 = Find(R1), r2 = Find(R2);int tmp = parent[r1] + parent[r2]; //两个集合结点个数之和(负数)//如果R2所在树结点个数> R1所在树结点个数//注意parent[r1]和parent[r2]都是负数if( parent[r1] > parent[r2] ) //优化方案――加权法则{parent[r1] = r2; //将根结点r1所在的树作为r2的子树(合并)parent[r2] = tmp; //更新根结点r2的parent[ ]值}else{parent[r2] = r1; //将根结点r2所在的树作为r1的子树(合并)parent[r1] = tmp; //更新根结点r1的parent[ ]值}}字符串的kmp算法：#include<iostream>#include<ctime>#include<fstream>#include<cstdio>#include<cmath>#include<cstring>using namespace std;//ifstream fin("g.txt");//ofstream fout("g.out");char s[1000];char p[1000];int next[1000];int n,m;//长度void next_val(){int i,j;j=-1;i=0;next[0]=-1;while(i<m-1){if(j==-1||p[i]==p[j]){i++;j++;if(p[i]!=p[j])next[i]=j;elsenext[i]=next[j];}elsej=next[j];}}int index(){int i, j;i=0;j=-1;while(i<n&&j<m){if(j==-1||p[j]==s[i]){i++;j++;}elsej=next[j];}if(j>m-1) return i-m+1;elsereturn 0;}int main(){freopen("g.txt","r",stdin);int i;cin>>n;cin>>s;//主串cin>>m;cin>>p;//模式串next_val();for(i=0 ;i<m ;i++){cout<<next[i]+1;}cout<<endl;cout<<index()<<endl;return 0;}高斯消元解线性方程组double m[100][100];double b[100];double x[100];int n;int main(){cin>>n;int i,j,k;for(i=1; i<=n; i++){for(j=1; j<=n; j++)cin>>m[i][j];cin>>b[i];}for(i=1; i<n; i++)//消元{if(m[i][i]==0)//判断是否为0，为就更最近一行（不为0换）{for(j=i+1; j<=n; j++)if(m[j][i]!=0){for(k=1; k<=n; k++){double t=m[i][k];m[i][k]=m[j][k];m[j][k]=t;}double t;t=b[i];b[i]=b[j];b[j]=t;}}if(m[i][i]==0) continue;都为0 就下也回合，for(k=i+1; k<=n; k++){if(m[k][i]==0)continue;for(j=i+1 ; j<=n; j++){m[k][j]-=(m[i][j]/m[i][i])*m[k][i];}b[k]-=(b[i]/m[i][i])*m[k][i];m[k][i]=0;}}//回带过程if(m[n][n]!=0)x[n]=b[n]/m[n][n];else if(b[n]==0)x[n]=0;else{cout<<"NO Solution!"<<endl;return 0;}for(i=n-1; i>=1; i--){for(j=n; j>i; j--){x[i]-=x[j]*m[i][j];}if(m[i][i]!=0)x[i]=(x[i]+b[i])/m[i][i];else if((b[i]+x[i])!=0){cout<<"NO Solution!"<<endl;return 0;}}for(i=1; i<=n; i++)cout<<x[i]<<" ";cout<<endl;return 0;}计算几何：#include<iostream>#include<algorithm>#include<iomanip>#include<cstdio>#include<cmath>#include<ctime>#define Abs(x) (((x)<0)?(-(x)):(x))#define Max(a,b) (((a)>(b))?(a):(b))#define Min(a,b) ((a)<(b))?(a):(b)))#define Epsilon 1e-10#define infinity 1e+10#define PI 3.14159265358979323846using namespace std;struct POINT{double x;double y;POINT():x(0),y(0){};POINT(double _x, double _y):x(_x),y(_y){}; };struct LINE{double a,b,c;POINT A;POINT B;LINE() {};LINE( POINT _a, POINT _b){A=_a;B=_b;a=B.y-A.y;b=A.x-B.x;c=B.x*A.y-A.x*B.y;};};struct RECT{POINT a;POINT b;RECT() {};RECT ( POINT _a, POINT _b):a(_a),b(_b){};};struct SEG{POINT a;POINT b;SEG() {};SEG(POINT _a, POINT _b):a(_a), b(_b) {};};struct TRIANGLE{POINT a,b,c;TRIANGLE() {};TRIANGLE(POINT _a,POINT _b,POINT _c):a(_a),b(_b),c(_c) {}; };struct CIRCLE{double x;double y;double r;CIRCLE() {};CIRCLE(double _x,double _y,double _r): x(_x), y(_y), r(_r){}; };struct POLY{int n;double *x;double *y;POLY() :n(0),x(NULL), y(NULL){};POLY(int _n, const double *_x, const double *_y){n=_n;x=new double[n+1];memcpy(x,_x,n*sizeof(double));x[n]=_x[n];y=new double[n+1];memcpy(y,_y, n*sizeof(double));y[n]=_y[n];}};double Cross(POINT a,POINT b, POINT o){return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);}SEG Edge(const POLY & poly, int idx){idx%=poly.n;return SEG(POINT(poly.x[idx],poly.y[idx]),POINT(poly.x[idx+1],poly.y[idx+1]));}bool IsEqual(double a, double b){return (Abs(a-b)<Epsilon);}bool IsEqual(const POINT & a, const POINT & b){return (IsEqual(a.x,b.x)&&IsEqual(a.y,b.y));}void Coefficient(const LINE & L, double &A, double &B, double &C){A=L.a;B=L.b;C=L.c;}void Coefficient(const SEG &AB,double &A, double &B, double &C )线段系数{A=AB.b.y-AB.a.y;B=AB.a.x-AB.b.x;C=AB.b.x*AB.a.y-AB.a.x*AB.b.y;}bool IsEqual(const LINE &A, const LINE &B)判断两直线是否一样{double A1,B1,C1;double A2,B2,C2;Coefficient(A,A1,B1,C1);Coefficient(B,A2,B2,C2);return IsEqual(A1*B2,A2*B1)&&IsEqual(A1*C2,A2*C1)&&IsEqual(B1*C2,B2*C1);}bool IsOnSeg(const SEG & seg, const POINT & p)判断点是否在线段上{if(Cross(seg.a,seg.b,p)!=0) return false;if((p.x>seg.a.x&&p.x>seg.b.x)||(p.x<seg.a.x&&p.x<seg.b.x))return false;if((p.y>seg.a.y&&p.y>seg.b.y)||(p.y<seg.a.y&&p.y<seg.b.y))return false;return true;}bool IsIntersect(const SEG & L1, const SEG &L2)//判断线段是否相交{return (Cross(L1.a,L2.a,L1.b)*Cross(L1.a,L2.b,L1.b)<=0)&& (Cross(L2.a,L1.a,L2.b)*Cross(L2.a,L1.b,L2.b)<=0);}bool IsParallel(const LINE &A, const LINE &B)判断直线是否平行{double A1 ,B1, C1;double A2, B2, C2;Coefficient(A,A1,B1,C1);Coefficient(B,A2,B2,C2);return (A1*B2==A2*B1)&&((A1*C2!=A2*C1||B1*C2!=B2*C1));}POINT Intersection(const LINE &A, const LINE &B)//求直线交点{double A1,B1,C1;double A2,B2,C2;Coefficient(A,A1,B1,C1);Coefficient(B,A2,B2,C2);POINT I(0,0);if(A1*B2-A2*B1!=0){I.x=-(B2*C1-B1*C2)/(A1*B2-A2*B1);I.y=(A2*C1-C2*A1)/(A1*B2-A2*B1);}return I;}POINT Intersection(const SEG & A, const SEG & B)//求线段的交点{double A1,B1,C1;double A2,B2,C2;Coefficient(A,A1,B1,C1);Coefficient(B,A2,B2,C2);POINT I(0,0);if(A1*B2-A2*B1!=0){I.x=-(B2*C1-B1*C2)/(A1*B2-A2*B1);I.y=(A2*C1-C2*A1)/(A1*B2-A2*B1);}return I;}bool IsInCircle(const CIRCLE & circle, const RECT & rect)判断矩形是否在圆内{return (circle.x-circle.r<=rect.a.x)&&(circle.x+circle.r>=rect.b.x)&&(circle.y-circle.r<=rect.a.y)&&(circle.y+circle.r>=rect.b.y);}bool IsSimple(const POLY &poly)判断是否为简单多边形{if(poly.n<3)return false;SEG L1,L2;for(int i=0; i<poly.n; i++){L1=Edge(poly,i);for(int j=i+1;j<poly.n; j++){L2=Edge(poly,j);if(j==i+1){if(IsOnSeg(L1,L2.b)||IsOnSeg(L2,L1.a))return false;}else if(j==poly.n-i-1){if(IsOnSeg(L1,L2.a)||IsOnSeg(L2,L1.b))return false;}else{if(IsIntersect(L1,L2))return false;}}}return true;}double Area(const POLY &poly ) 多边形的面积{if(poly.n<3) return 0;double s=poly.y[0]*(poly.x[poly.n-1]-poly.x[1]);for(int i=1; i<poly.n; i++){s+=poly.y[i]*(poly.x[i-1]-poly.x[(i+1)%poly.n]);}return s/2;}double Area1(const POLY & poly)多边形的面积{if(poly.n<3) return 0;double s=0.0;POINT p0(poly.x[0],poly.y[0]);for(int i=1; i<poly.n-1;i++){POINT p1(poly.x[i],poly.y[i]),p2(poly.x[i+1],poly.y[i+1]);s+=Cross(p1,p2,p0);}return s/2;}bool IsOnPoly(const POLY & poly, const POINT & p)判断点在多边形边上{for(int i=0; i< poly.n; i++){if(IsOnSeg(Edge(poly,i),p))return true;}return false;}bool IsInPoly(const POLY &poly, const POINT & p)判断点在多边形内{SEG L(p,POINT(infinity,p.y));//射线int count=0;for(int i=0; i<poly.n;i++){SEG s=Edge(poly, i);if(IsOnSeg(s,p)){return false;}if(!IsEqual(s.a.y,s.b.y)){POINT &q=(s.a.y>s.b.y)?s.a:s.b;if(IsOnSeg(L,q)){++count;}else if(!IsOnSeg(L,s.a)&&!IsOnSeg(L,s.b)&&IsIntersect(s,L)){++count;}}}if(count==1)return true;elsereturn false;}double distance(POINT a, POINT b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}POINT Point;bool comp(POINT &x, POINT &y){return Cross(x,y,Point)>0||(Cross(x,y,Point)==0&&distance(x,Point)>distance(y,Point)); }void Swap(POINT &x ,POINT &y){POINT z=x;x=y; y=z;}POLY ConvexHull(POINT p[],int n)求简单多边形的凸包{int i,k=0;for(i=1; i<n; i++)if(p[k].y>p[i].y||(p[k].y==p[i].y&&p[k].x>p[i].x))k=i;Swap(p[0],p[k]);Point.x=p[0].x;Point.y=p[0].y;sort(p+1,p+n,comp);int top=2;double x[100];double y[100];x[0]=p[0].x; y[0]=p[0].y;x[1]=p[1].x; y[1]=p[1].y;x[2]=p[2].x; y[2]=p[2].y;for( i=3; i<n; i++){while(Cross(p[i],POINT(x[top],y[top]),POINT(x[top-1],y[top-1]))>=0) top--;++top;x[top]=p[i].x;y[top]=p[i].y;}POLY poly(top,x,y);return poly;}double Cross(POINT a, POINT b){return a.x*b.y-a.y*b.x;}double triArea(TRIANGLE t)//三角形面积叉积法{return fabs(Cross(t.a,t.b)+Cross(t.b,t.c)+ Cross(t.c,t.a))/2.0;}double Pow(double x){return x*x;}CIRCLE waiyuan(TRIANGLE t)//求三角形的外切圆{CIRCLE tmp;double a,b,c,c1,c2;double ax,ay,bx,by,cx,cy;a=distance(t.a,t.b);b=distance(t.b,t.c);c=distance(t.c,t.a);tmp.r=a*b*c/triArea(t)/4;ax=t.a.x; ay=t.a.y;bx=t.b.x; by=t.b.y;cx=t.c.x; cy=t.c.y;c1=(Pow(ax)+Pow(ay)-Pow(bx)-Pow(by))/2;c2=(Pow(ax)+Pow(ay)-Pow(cx)-Pow(cy))/2;tmp.x=(c1*(ay-cy)-c2*(ay-by))/((ax-bx)*(ay-cy)-(ax-cx)*(ay-by));tmp.y=(c1*(ax-cx)-c2*(ax-bx))/((ay-by)*(ax-cx)-(ay-cy)*(ax-bx));return tmp;}CIRCLE neiyuan(TRIANGLE t)求三角形的内切圆{CIRCLE tmp;double a,b,c,angleA,angleB, angleC,p,p2,p3,f1,f2;double ax,bx,cx,ay,by,cy;a=distance(t.a, t.b);b=distance(t.b,t.c);c=distance(t.c, t.a);tmp.r=2*triArea(t)/(a+b+c);//内切圆半径angleA=acos((b*b+c*c-a*a)/(2*b*c));angleB=acos((a*a+c*c-b*b)/(2*a*c));angleC=acos((a*a+b*b-c*c)/(2*a*b));p=sin(angleA/2); p2=sin(angleB/2); p3=sin(angleC/2);ax=t.a.x; ay=t.a.y;bx=t.b.x; by=t.b.y;cx=t.c.x; cy=t.c.y;f1=(Pow(tmp.r/p2)-Pow(tmp.r/p)+Pow(ax)-Pow(bx)+Pow(ay)-Pow(by))/2;f2=(Pow(tmp.r/p3)-Pow(tmp.r/p)+Pow(ax)-Pow(cx)+Pow(ay)-Pow(cy))/2;tmp.x=(f1*(ay-cy)-f2*(ay-by))/((ax-bx)*(ay-cy)-(ax-cx)*(ay-by));tmp.y=(f1*(ax-cx)-f2*(ay-by))/((ay-by)*(ax-cx)-(ay-cy)*(ax-bx));return tmp;}bool IspointIntri(TRIANGLE t, const POINT & p)//点在三角形内还是外？{double k1,k2,k3;k1=Cross(t.a,t.b,p);k2=Cross(t.b,t.c,p);k3=Cross(t.c,t.a,p);cout<<k1<<" "<<k2<<" "<<k3<<endl;if(k1*k2<0) return false;if(k1*k3<0) return false;return true;}POINT duichendiandian(POINT p1, POINT p2)//对称点点对点{POINT p3;p3.x=2*p2.x-p1.x;p3.x=2*p2.x-p1.y;return p3;}POINT duicedianxian(POINT p, LINE l)//点对线对称{POINT p2;double d;d=l.a*l.a + l.b*l.b;p2.x=(l.b*l.b*p.y-l.a*l.a*p.x-2*l.a*l.b*p.y-2*l.a*l.c)/d;p2.y=(l.a*l.a*p.y-l.b*l.b*p.y-2*l.a*l.b*p.x-2*l.b*l.c)/d;return p2;}double diandaoxianjuli(POINT p, LINE l)//点到线的距离{return fabs(l.a*p.x+l.b*p.y+l.c)/sqrt(l.a*l.a+l.b*l.b);}double xili(LINE l){if(l.b!=0)return -(l.a/l.b);elsereturn infinity;}int main(){POINT a(0,0),b(1,0),c(0,1),d(-1,3),e(0,2),f(2,0),g(2,2);CIRCLE o(0,0,2);RECT s(d,a);LINE A(a,c),B(c,e);SEG AB(a,b),BC(f,g);double x[10]={2,3,2,1,0,1,0,1.5,1.6,0.1};double y[10]={0,1,2,2,1,0,0,1.5,1.6,0.5};POINT po[10];for(int i=0; i<10;i++){po[i].x=x[i];po[i].y=y[i];}POLY p(6,x,y);if(IsEqual(a,b)) cout<<"yes"<<endl;else cout<<"NO"<<endl;if(IsEqual(A,B)) cout<<"yes"<<endl;else cout<<"NO"<<endl;if(IsParallel(A,B)) cout<<"yes"<<endl;else cout<<"NO"<<endl;if(IsIntersect(AB,BC)) cout<<"yes"<<endl;else cout<<"No"<<endl;POINT w=Intersection(AB,BC);cout<<w.x<<" "<<w.y<<endl;if(IsInCircle(o,s)) cout<<"yes"<<endl;else cout<<"no"<<endl;if(IsSimple(p)) cout<<"yes"<<endl;time_t cb=clock();double s1=Area(p);time_t cd1=clock();double s2=Area1(p);if(IsInPoly(p,f)||IsOnPoly(p,f)) cout<<"yes"<<endl; else cout<<"no"<<endl;POLY poly=ConvexHull(po,10);for(i=0; i<=poly.n;i++)cout<<poly.x[i]<<" "<<poly.y[i]<<endl;time_t cd2=clock();cout<<s1<<" "<<s2<<endl;cout<<endl;TRIANGLE t;POINT a1(-2,0),a2(2,0),a3(0,2),a4(0,1),a5(3,5),a6(0,0); t.a=a1; t.b=a2; t.c=a3;cout<<"三角形面积"<<triArea(t)<<endl; CIRCLE C=waiyuan(t);cout<<C.r<<" "<<C.x<<" "<<C.y<<endl;C=neiyuan(t);cout<<C.r<<" "<<C.x<<" "<<C.y<<endl;cout<<"点是不是在三角形内"<<IspointIntri(t,a1)<<endl;cout<<IspointIntri(t,a4)<<endl;cout<<IspointIntri(t,a5)<<endl;cout<<"p1对P2的对称点P3"<<endl;POINT p3=duichendiandian(a3,a4);cout<<p3.x<<" "<<p3.y<<endl;cout<<"点对线的对称点"<<endl;LINE L(a3,a5);p3=duicedianxian(a6,L);cout<<p3.x<<" "<<p3.y<<endl;cout<<cd1-cb<<" "<<cd2-cb<<endl;cout<<"点到直线的距离"<<endl;cout<<diandaoxianjuli(a4,L)<<endl;cout<<xili(L)<<endl;char q;cin>>q;return 1;}Wallacstruct POINT{double x ,y;POINT (): x(0),y(0){};POINT ( double _a, double _b): x(_a), y(_b){};};double Cross(POINT a, POINT b, POINT o){return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);}double Pow(double x){return x*x;}double distance(POINT a, POINT b){return sqrt(Pow(a.x-b.x)+Pow(a.y-b.y));}POINT Point;bool comp(POINT &x, POINT & y){return ( Cross(x,y,Point)>0||(Cross(x,y,Point)==0&&( distance(x,Point) > distance(y,Point) ) )); }void Swap(POINT &x, POINT &y){POINT z=x;x=y; y=z;}int n,l;POINT p[1000];POINT p1[1000];int top=0;int main(){int i;cin>>n>>l;for(i=0; i<n; i++)cin>>p[i].x>>p[i].y;int k=0;for(i=1; i<n; i++){if(p[i].y<p[k].y||(p[i].y==p[k].y&&p[i].x<p[k].x))k=i;}Swap(p[0],p[k]);Point=p[0];sort(p+1,p+n,comp);p1[0]=p[0];p1[1]=p[1];p1[2]=p[2];top=2;for(i=3; i<n; i++){while(Cross(p[i],p1[top],p1[top-1])>0) --top;++top;p1[top]=p[i];}double sum=0.0;cout<<top<<endl;for(i=0; i<top; i++){sum+=distance(p1[i],p1[i+1]);cout<<p1[i].x<<" "<<p1[i].y<<endl;}sum+=distance(p1[top],p1[0]);cout<<sum<<" "<<2*pi*l<<endl;long z=(sum+2*pi*l+0.5);cout<<z<<endl;return 0;}最小半径圆：#include<cstdio>#include<iostream>using namespace std;#include<cmath>#define maxn 1000#define eps 1e-6struct POINT{double x, y;POINT():x(0),y(0){};};struct Circle{double r;POINT center;};struct Triangle{POINT a,b,c;};POINT a[maxn+1];Circle c;int casenum, n;double Pow(double x){return x*x;}double distance(POINT a, POINT b){return sqrt(Pow(a.x-b.x)+Pow(a.y-b.y)); }double Cross(POINT a, POINT b, POINT o){return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x); }double triangleArea(POINT t[3]){return fabs(Cross(t[0],t[1],t[2]))/2;}Circle circleoftriangle(POINT t[3]){Circle tmp;double a,b,c,c1,c2;double ax,ay,bx,by,cx,cy;a=distance(t[0],t[1]);b=distance(t[1],t[2]);c=distance(t[2],t[0]);tmp.r=a*b*c/triangleArea(t)/4;ax=t[0].x; ay=t[0].y;bx=t[1].x; by=t[1].y;cx=t[2].x; cy=t[2].y;c1=(Pow(ax)+Pow(ay)-Pow(bx)-Pow(by))/2; c2=(Pow(ax)+Pow(ay)-Pow(cx)-Pow(cy))/2; tmp.center.x=(c1*(ay-cy)-c2*(ay-by))/((ax-bx)*(ay-cy)-(ax-cx)*(ay-by)); tmp.center.y=(c1*(ax-cx)-c2*(ax-bx))/((ay-by)*(ax-cx)-(ay-cy)*(ax-bx)); return tmp;}Circle MinCircle2(int tce, POINT ce[3]){Circle tmp;tmp.center.x=0;tmp.center.y=0;tmp.r=0;switch(tce){case 0: tmp.r=-2;break;case 1: {tmp.center=ce[0];}break;case 2: {tmp.r=distance(ce[0],ce[1])/2;tmp.center.x=(ce[0].x+ce[1].x)/2;tmp.center.y=(ce[0].y+ce[1].y)/2;} break;case 3:{tmp=circleoftriangle(ce);} break;}return tmp;}void Swap(POINT &x, POINT &y){POINT z=x; x=y; y=z;}bool inCirclr(POINT p , Circle c){return distance(p, c.center)<c.r+eps;}void MinCircle(int t, int tce, POINT ce[3]){int i;POINT tmp;c=MinCircle2(tce,ce);if(tce==3) return;for(i=1;i<=t; i++){if(distance(a[i],c.center)>c.r+eps){ce[tce]=a[i];MinCircle(i-1,tce+1,ce);}}}void run(){POINT ce[3];MinCircle(n,0,ce);printf("%.2f %.2f %.2f\n",c.center.x,c.center.y,c.r); }int main(){cin>>casenum;int i;while(casenum>0){cin>>n;for(i=1; i<=n; i++)cin>>a[i].x>>a[i].y;run();casenum--;}}//数论模板#include<iostream>#include<cmath>using namespace std;//辗转相除法求最大公约数long gcd(long a, long b){if(b==0)return a;elsereturn gcd(b,a%b);}//求最大公倍数long lcm(long a, long b){if(a*b==0) return 0;elsereturn a*b/gcd(a,b);}//求a^b mod nlong modexp(long a, long b, long n){int t, y;t=1; y=a;while(b!=0){if(b&1==1)t=t*y%n;y=y*y%n;b/=2;}return t;}//扩展的Euclid算法//返回a.b的最大公约数，并使ax+by=d; long exEuclid(long a, long b, long & x, long & y) {long tmp,d;if(b==0){y=0;return a;}d=exEuclid(b, a%b, x,y);tmp=x;x=y;y=tmp-a/b*y;return d;}//解线性同余方程ax=b(mod n)//返回最小的xlong modu(long a, long b, long n){long d,x=1,y=0;d=exEuclid(a,n,x,y);x=x*(b/d);x=(x%(n/d)+n/d)%(n/d);return x;}//用中国剩余定理解同余方程组a=bi（modni) long solmodu(long z, long b[], long n[]){int i;long a,m,x,y,t;m=1 ;a=0;for(i=0; i<z; i++) m*=n[i];for(i=0; i<z; i++){t=m/n[i];exEuclid(n[i],t,x,y);a=(a+t*y*b[i])%m;}return (a+m)%m;}//筛法求素数const maxn=100000;bool prime[maxn+1];void searchprime(long b[],long & k){int i ,j;memset(prime,0,sizeof(prime));prime[1]=1;for(i=2; i<sqrt(maxn); i++)if(!prime[i]){j=i*2;while(j<=maxn){prime[j]=1;j+=i;}}j=0;for(i=1; i<maxn; i++)if(prime[i]==0)b[j++]=i;k=j;}//判定素数素数表bool isPrime(long x,long b[]){int i;i=1;while(b[i]*b[i]<=x){if(x%b[i]==0)return 0;i++;}return true;}//判定素数，概率方法bool passTest(long n){long l ,m,b,i,k;m=n-1;l=0;while(m%2==0){l++;m/=2;}b=rand()%n+1;if(modexp(b,m,n)==1) return 1;k=m;for(i=0; i<l; i++){if(modexp(b,k,n)==n-1) return 1;k*=2;}return 0;}取子游戏#include <iostream>#include <cmath>using namespace std;int main(){double alpha = (1.0 + sqrt(5.0)) / 2.0;double beta = (3.0 + sqrt(5.0)) / 2.0;int big, small, n, temp1, temp2;while(cin>>big>>small){if(big < small)swap(big, small);n = ceil(big / beta);temp1 = alpha * n;temp2 = beta * n;if(small == temp1 && big == temp2)cout<<0<<endl;else cout<<1<<endl;}return 0;}二维树状数组1195#include<cstdio>#include<iostream>using namespace std;int c[1025][1025];int n, cmd;static inline int lastexp(int i){return i&(-i);}void modify(int x, int y, int a){int i, j;for(i=x; i<=n; i+=lastexp(i))for(j=y; j<=n; j+=lastexp(j))c[i][j]+=a;}long getsum(int x, int y){long total=0;int i, j;for(i=x; i>0; i-=lastexp(i))for(j=y; j>0; j-=lastexp(j))total+=c[i][j];return total;}void modify1(){int x, y, a;scanf("%d%d%d",&x,&y,&a);x++;y++;modify(x,y,a);}long getsum1(){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);a++; b++; c++; d++;return getsum(c,d)-getsum(c,b-1)-getsum(a-1,d)+getsum(a-1,b-1); }int main(){long s;while(1){cin>>cmd;switch(cmd){case 0: memset(c,0,sizeof(c)); cin>>n; break;case 1: modify1(); break;case 2: s=getsum1(); printf("%ld\n",s); break;case 3: goto L;}}L: return 0;}图论模板最小生成树：1 prime算法：#include<iostream>#include<fstream>using namespace std;#define maxn 201#define Max 10000ifstream fin("g.txt");int g[maxn][maxn];int best[maxn];bool s[maxn];int bian[maxn];int sum,n;void Prim(int k){int i,j;bian[k]=-1;best[k]=0;for(i=1; i<=n; i++){int min=Max;int t=k;for(j=1; j<=n; j++)if(!s[j]&&min>best[j]){min=best[j];t=j;}s[t]=1;sum+=min;for(j=1; j<=n; j++)if(!s[j]&&g[t][j]>0&&best[j]>g[t][j]){best[j]=g[t][j];bian[j]=t;}}}int main(){int i, j;fin>>n;for(i=1; i<=n;i++)for(j=1; j<=n; j++)fin>>g[i][j];memset(s,0,sizeof(s));memset(best,10000,sizeof(best));Prim(1);for(j=n; j>1;j-- )cout<<bian[j]<<" "<<j<<endl;cout<<sum<<endl;return 0;}2 kruskal算法：#include<iostream>#include<fstream>#include<algorithm>using namespace std;ifstream fin("g.txt");struct Edge{int x,y,c;};int g[100][100];int pa[100];int root[100];Edge b[1000];int n,e,sum=0;bool comp(Edge &x, Edge &y){return x.c<y.c;}int Find(int x){int i,j=x;while(!root[j]) j=pa[j];while(j!=x)//路劲压缩都指向j（树根）{i=pa[x];pa[i]=j;x=i;}return j;}void Union(int x, int y){if(pa[x]<pa[y]){pa[y]+=pa[x];root[x]=0;pa[x]=y;}else{pa[x]+=pa[y];root[y]=0;pa[y]=x;}}void Kruskal(){sort(b,b+e,comp);int i,j=0,sum=0;for(i=0; i<e;i++){int a,c;a=Find(b[i].x);c=Find(b[i].y);//注意a，c是所在边上点的根结点；if(a!=c){sum+=b[i].c;cout<<b[i].x<<" "<<b[i].y<<endl；Union(a,c);j++;}if(j==n-1) break;}cout<<sum<<endl;}int main(){int i, j;fin>>n;e=0;for(i=1; i<=n; i++){pa[i]=1;root[i]=1;for(j=1; j<=n;j++){fin>>g[i][j];if(j>i&&g[i][j]>0){b[e].c=g[i][j];b[e].x=i;b[e].y=j;e++;}}}Kruskal();return 0;}二最短路Dijkstra算法：1.#include<iostream>#include<fstream>using namespace std;#define MAX 10000#define maxn 201ifstream fin("g.txt");int g[100][100];int d[100];int p[100];bool s[100];int n;void dijkstra(int k){d[k]=0;int i,j;for(i=2; i<=n; i++){int min=MAX;int t=k;for(j=1 ;j<=n; j++)if(!s[j]&&d[j]<min){min=d[j];t=j;}s[t]=1;for(j=1; j<=n; j++)if(!s[j]&&g[t][j]>0&&d[j]>d[t]+g[t][j]){d[j]=d[t]+g[t][j];p[j]=t;}}}int main(){int i,j;fin>>n;for(i=1; i<=n ;i++)for(j=1; j<=n ; j++)fin>>g[i][j];memset(d,10000,sizeof(d));memset(s,0,sizeof(s));p[1]=0;dijkstra(1);for(i=1; i<= n; i++){cout<<"1---"<<i<<" ";cout<<d[i]<<" ";j=i;while(j){cout<<j<<" ";j=p[j];}cout<<endl;}return 0;}2 Bellman_Ford算法：#include<iostream>#include<fstream>#include<deque>using namespace std;#define MAX 10000#define maxn 201ifstream fin("g.txt");int g[100][100];int d[100];int count[100];int p[100];int n;deque<int> Q;bool Bellman_Ford(int k){Q.push_back(k);int j;d[k]=0;while(!Q.empty()){int i=Q.front();Q.pop_front();count[i]++;if(count[i]>n) return false;for(j=1; j<=n; j++)if(g[i][j]!=0&&d[j]>d[i]+g[i][j]){d[j]=d[i]+g[i][j];p[j]=i;Q.push_back(j);}}return true;}int main(){int i,j;fin>>n;memset(count,0,sizeof(count));for(i=1;i<=n;i++)for(j=1;j<=n;j++)fin>>g[i][j];memset(d,10000,sizeof(d));p[1]=0;bool b=Bellman_Ford(1);if(b){for(i=1;i<=n;i++){cout<<"1---"<<i<<" ";cout<<d[i]<<" ";j=i;while(j){cout<<j<<" ";j=p[j];}cout<<endl;}}elsecout<<"qw"<<endl;return 0;}三图的dfs应用链表拓扑排序（有向图）割点桥。

高精度 .......................................................................................................................2 (1)高精函数 ........................................................................................................2 (2)高精开方 ........................................................................................................6 (3)高精类............................................................................................................9 计算几何 .................................................................................................................13 (1)凸包..............................................................................................................13 (2)最远点对 ..............................................................................................

2 数论........................................................................................................................................... 21
2.1 最大公约数 gcd............................................................................................................21 2.2 最小公倍数 lcm............................................................................................................22
3.1 堆（最小堆）...............................................................................................................31
3.1.1 3.1.2
删除最小值元素：.......................................................................................... 31 插入元素和向上调整：.................................................................................. 32
1.5 拓扑排序.........................................................................................................................7

专用模板目录：一、图论1．最大团2．拓扑排序3．最短路和次短路4．SAP模板5．已知各点度，问能否组成一个简单图6．KRUSKAL7. Prim算法求最小生成树8. Dijkstra9 . Bellman-ford10. SPFA11. Kosaraju 模板12. tarjan 模板二、数学1. 剩余定理2. N!中质因子P的个数3.拓展欧几里得4.三角形的各中心到顶点的距离和5.三角形外接圆半径周长6.归并排序求逆序数7. 求N！的位数8.欧拉函数9. Miller-Rabin,大整数分解，求欧拉函数10. 第一类斯特林数11.计算表达式12.约瑟夫问题13．高斯消元法14. Baby-step,giant-step n是素数.n任意15. a^b%c=a ^(b%eular(c)+eular(c)) % c16.判断第二类斯特林数的奇偶性17.求组合数C(n,r)18.进制转换19.Ronberg算法计算积分20.行列式计算21. 返回x 的二进制表示中从低到高的第i位22.高精度运算 +-*/23.超级素数筛选三、数据结构1．树状数组2.线段树求区间的最大、小值3.线段树求区间和4.单调队列5.KMP模板6. 划分树，求区间第k小数7.最大堆，最小堆模板8. RMQ模板求区间最大、最小值9.快速排序，归并排序求逆序数.10.拓展KMP四、计算几何1.凸包面积2.Pick公式求三角形内部有多少点3.多边形边上内部各多少点以及面积pick4.平面最远点对5.判断矩形是否在矩形内6.判断点是否在多边形内7.判断4个点(三维)是否共面8.凸包周长9.等周定理变形一直两端点和周长求最大面积10.平面最近点对11.单位圆最多覆盖多少点(包括边上)12.多边形费马点求点到多边形各个点的最短距离13.矩形并周长14.zoj 2500 求两球体积并一、图论1.最大团#include<iostream>#include<algorithm>using namespace std;int n,m;int cn;//当前顶点数int best;//当前最大顶点数int vis[50];//当前解int bestn[50];//最优解int map[50][50];//临界表void dfs(int i){if(i>n){for(int j=1;j<=n;j++) bestn[j]=vis[j];best=cn;return ;}int ok=1;for(int j=1;j<i;j++){if(vis[j]==1&&map[i][j]==0){ok=0;break;}}if(ok){//进入左子树vis[i]=1;cn++;dfs(i+1);cn--;}if(cn+n-i>best){//进入右子树vis[i]=0;dfs(i+1);}}int main(){while(scanf("%d%d",&n,&m)==2){memset(vis,0,sizeof(vis));memset(map,0,sizeof(map));while(m--){int p,q;scanf("%d%d",&p,&q);map[p][q]=map[q][p]=1;//无向图}cn=0;best=0;dfs(1);printf("%d\n",best);}return 0;}2.拓扑排序#include<iostream>#include<cstring>using namespace std;int map[105][105],in[105],vis[105],ans[105],n;int flag;void dfs(int step){if(flag) return ;if(step==n+1) {flag=1; printf("%d",ans[1]);for(int i=2;i<=n;i++) printf(" %d",ans[i]);printf("\n");return ;}for(int i=1;i<=n;i++){if(vis[i]==0&&in[i]==0){vis[i]=1;for(int j=1;j<=n;j++){if(map[i][j]>0){map[i][j]=-map[i][j];in[j]--;}}ans[step]=i;dfs(step+1);vis[i]=0;for(int j=1;j<=n;j++){if(map[i][j]<0){map[i][j]=-map[i][j];in[j]++;}}}}}int main(){while(scanf("%d",&n)==1){flag=0;memset(map,0,sizeof(map));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));for(int i=1;i<=n;i++){int t;while(scanf("%d",&t),t){map[i][t]=1;in[t]++;}}dfs(1);}return 0;}3．最短路和次短路#include<iostream>#include<cstdio>#include<vector>#include<cstring>using namespace std;class Node{public:int e,w;//表示终点和边权};const int inf=(1<<25);int main(){int ci;cin>>ci;while(ci--){vector<Node> G[1005];//用邻接表存边int n,m;cin>>n>>m;for(int i=1;i<=m;i++){Node q;int u;cin>>u>>q.e>>q.w;G[u].push_back(q);}int s,f;//起点和终点cin>>s>>f;//dijkstra 求最短路和次短路int flag[1005][2];int dis[1005][2],cnt[1005][2];//0表示最短路，1表示次短路memset(flag,0,sizeof(flag));for(int i=1;i<=n;i++) dis[i][0]=dis[i][1]=inf;dis[s][0]=0;cnt[s][0]=1;//初始化for(int c=0;c<2*n;c++) //找最短路和次短路，故要进行2*n次循环也可以改成while(1){int temp=inf,u=-1,k;//找s-S'集合中的最短路径,u记录点的序号，k记录是最短路或者是次短路for(int j=1;j<=n;j++){if(flag[j][0]==0&&temp>dis[j][0]) temp=dis[j][0],u=j,k=0;else if(flag[j][1]==0&&temp>dis[j][1]) temp=dis[j][1],u=j,k=1;}if(temp==inf) break;//S'集合为空或者不联通，算法结束//更新路径flag[u][k]=1;for(int l=0;l<G[u].size();l++){int d=dis[u][k]+G[u][l].w,j=G[u][l].e;//important//4种情况if(d<dis[j][0]){dis[j][1]=dis[j][0];cnt[j][1]=cnt[j][0];dis[j][0]=d;cnt[j][0]=cnt[u][k];}else if(d==dis[j][0]){cnt[j][0]+=cnt[u][k];}else if(d<dis[j][1]){dis[j][1]=d;cnt[j][1]=cnt[u][k];}else if(d==dis[j][1]){cnt[j][1]+=cnt[u][k];}}}int num=cnt[f][0];//最短路int cc=cnt[f][1];//次短路}return 0;}4．SAP模板#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int inf=(1<<31)-1;const int point_num=300;int cap[point_num][point_num],dist[point_num],gap[point_num];//初始化见main里面int s0,t0,n;//源,汇和点数int find_path(int p,int limit=0x3f3f3f3f){if(p==t0) return limit;for(int i=0;i<n;i++)if(dist[p]==dist[i]+1 && cap[p][i]>0){int t=find_path(i,min(cap[p][i],limit));if(t<0) return t;if(t>0){cap[p][i]-=t;cap[i][p]+=t;return t;}}int label=n;for(int i=0;i<n;i++) if(cap[p][i]>0) label=min(label,dist[i]+1);if(--gap[dist[p]]==0 || dist[s0]>=n ) return -1;++gap[dist[p]=label];return 0;}int sap(){//初始化s,ts0=0,t0=n-1;int t=0,maxflow=0;gap[0]=n;while((t=find_path(s0))>=0) maxflow+=t;return maxflow;}int main(){int ci;while(cin>>ci>>n){//初始化memset(cap,0,sizeof(cap));memset(dist,0,sizeof(dist));memset(gap,0,sizeof(gap));//初始化capwhile(ci--){int x,y,c;cin>>x>>y>>c;x--;y--;cap[x][y]+=c;//因题而异}int ans=sap();cout<<ans<<endl;}return 0;}5．已知各点度，问能否组成一个简单图#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int inf=(1<<30);int d[1100];bool cmp(int x,int y){return x>y;}int main(){int ci;scanf("%d",&ci);while(ci--){int n,flag=1,cnt=0;scanf("%d",&n); for(int i=0;i<n;i++){scanf("%d",&d[i]);if(d[i]>n-1||d[i]<=0) flag=0; cnt+=d[i];}if(flag==0||cnt%2){printf("no\n");continue;}sort(d,d+n,cmp);for(int l=n;l>0;l--){for(int i=1;i<l&&d[0];i++){d[0]--,d[i]--;if(d[i]<0){flag=0;break;}}if(d[0]) flag=0;if(flag==0) break;d[0]=-inf;sort(d,d+l,cmp);}if(flag) printf("yes\n");else printf("no\n");}return 0;}6.KRUSKAL#include<iostream>#include<algorithm>using namespace std;int u[15005],v[15005],w[15005],fath[15005],r[15005];int ans1[15005],ans2[15005];bool cmp(int i,int j){return w[i]<w[j];}int find(int x){return fath[x]==x?x:fath[x]=find(fath[x]);}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) fath[i]=i;for(int i=1;i<=m;i++) r[i]=i;for(int i=1;i<=m;i++){cin>>u[i]>>v[i]>>w[i];}sort(r+1,r+m+1,cmp);int maxn=0,ans=0,k=0;for(int i=1;i<=m;i++){int e=r[i];int x=find(u[e]),y=find(v[e]);if(x!=y){ans+=w[e];fath[x]=y;if(w[e]>maxn) maxn=w[e];ans1[k]=u[e];ans2[k++]=v[e];}}return 0;}7.prime求最小生成树语法：prim(Graph G,int vcount,int father[]);参数：G：图，用邻接矩阵表示vcount：表示图的顶点个数father[]：用来记录每个节点的父节点返回值：null注意：常数max_vertexes 为图最大节点数常数infinity为无穷大源程序：#define infinity 1000000#define max_vertexes 5typedef int Graph[max_vertexes][max_vertexes];void prim(Graph G,int vcount,int father[]){int i,j,k;intlowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes]; for (i=0;i<vcount;i++){lowcost[i]=G[0][i];closeset[i]=0;used[i]=0;father[i]=-1;}used[0]=1;for (i=1;i<vcount;i++){j=0;while (used[j]) j++;for (k=0;k<vcount;k++)if ((!used[k])&&(lowcost[k]<lowcost[j])) j=k;father[j]=closeset[j];used[j]=1;for (k=0;k<vcount;k++)if (!used[k]&&(G[j][k]<lowcost[k])){ lowcost[k]=G[j][k];closeset[k]=j; }}}8.Dijkstra语法：result=Dijkstra(Graph G,int n,int s,int t, int path[]); 参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径返回值：最短路径长度注意：输入的图的权必须非负顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Dijkstra(Graph G,int n,int s,int t, int path[]){int i,j,w,minc,d[max_vertexes],mark[max_vertexes];for (i=0;i<n;i++) mark[i]=0;for (i=0;i<n;i++){ d[i]=G[s][i];path[i]=s; }mark[s]=1;path[s]=0;d[s]=0;for (i=1;i<n;i++){minc=infinity;w=0;for (j=0;j<n;j++)if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}mark[w]=1;for (j=0;j<n;j++)if((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j])){ d[j]=d[w]+G[w][j];path[j]=w; }}return d[t];}9.Bellman-ford语法：result=Bellman_ford(Graph G,int n,int s,int t,int path[],int success);参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径success：函数是否执行成功返回值：最短路径长度注意：输入的图的权可以为负，如果存在一个从源点可达的权为负的回路则success=0顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Bellman_ford(Graph G,int n,int s,int t,int path[],int success){int i,j,k,d[max_vertexes];for (i=0;i<n;i++) {d[i]=infinity;path[i]=0;}d[s]=0;for (k=1;k<n;k++)for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]){d[j]=d[i]+G[i][j];path[j]=i;}success=0;for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]) return 0;success=1;return d[t];}10. SPFA#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;const __int64 maxn=1001000;const __int64 inf=1000100000;struct edge//邻接表{__int64 t,w;//s->t=w;__int64 next;//数组模拟指针};__int64 p[maxn],pf[maxn];//邻接表头节点edge G[maxn],Gf[maxn];//邻接表__int64 V,E;//点数[1-n] 边数__int64 dis[maxn];__int64 que[maxn],fro,rear;//模拟队列__int64 vis[maxn];__int64 inque[maxn];//入队次数bool spfa(__int64 s0){fro=rear=0;for(__int64 i=1;i<=V;i++) dis[i]=inf;dis[s0]=0;memset(vis,0,sizeof(vis));memset(inque,0,sizeof(inque));que[rear++]=s0;vis[s0]=1;inque[s0]++;while(fro!=rear){__int64 u=que[fro];fro++;if(fro==maxn) fro=0;vis[u]=0;for(__int64 i=p[u];i!=-1;i=G[i].next){__int64 s=u,t=G[i].t,w=G[i].w;if(dis[t]>dis[s]+w){dis[t]=dis[s]+w;if(vis[t]==0){que[rear++]=t,vis[t]=1;inque[t]++;if(inque[t]>V) return false;if(rear==maxn) rear=0;}}}}return true;}int main(){__int64 ci;scanf("%I64d",&ci);while(ci--){scanf("%I64d%I64d",&V,&E);memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf)); for(__int64 i=0;i<E;i++){__int64 u,v,w;scanf("%I64d%I64d%I64d",&u,&v,&w);G[i].t=v;G[i].w=w;G[i].next=p[u];p[u]=i;Gf[i].t=u;Gf[i].w=w;Gf[i].next=pf[v];pf[v]=i;}__int64 ans=0;spfa(1);//求第一个点到其他点的最短距离和for(__int64 i=1;i<=V;i++) ans+=dis[i];//反方向再来一次spfa 求其他点到第一个点的最短距离和 for(__int64 i=1;i<=V;i++) p[i]=pf[i];for(__int64 i=0;i<E;i++) G[i]=Gf[i];spfa(1);for(__int64 i=1;i<=V;i++) ans+=dis[i];printf("%I64d\n",ans);}return 0;}11.Kosaraju模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;struct edge{int t,w;//u->t=w;int next;};int V,E;//点数(从1开始)，边数int p[maxn],pf[maxn];//邻接表原图,逆图edge G[maxn],Gf[maxn];//邻接表原图,逆图int l,lf;void init(){memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf));l=lf=0;}void addedge(int u,int t,int w,int l){G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}void addedgef(int u,int t,int w,int lf){Gf[l].w=w;Gf[l].t=t;Gf[l].next=pf[u];pf[u]=l;}///Kosaraju算法,返回为强连通分量个数bool flag[maxn]; //访问标志数组int belg[maxn]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量int numb[maxn]; //结束时间(出栈顺序)标记,其中numb[i]表示离开时间为i的顶点//用于第一次深搜,求得numb[1..n]的值void VisitOne(int cur, int &sig){flag[cur] = true;for (int i=p[cur];i!=-1;i=G[i].next){if (!flag[G[i].t]){VisitOne(G[i].t,sig);}}numb[++sig] = cur;}//用于第二次深搜,求得belg[1..n]的值void VisitTwo(int cur, int sig){flag[cur] = true;belg[cur] = sig;for (int i=pf[cur];i!=-1;i=Gf[i].next){if (!flag[Gf[i].t]){VisitTwo(Gf[i].t,sig);}}//Kosaraju算法,返回为强连通分量个数int Kosaraju_StronglyConnectedComponent(){int i, sig;//第一次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=1; i<=V; ++i ){if ( false==flag[i] ){VisitOne(i,sig);}}//第二次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=V; i>0; --i ){if ( false==flag[numb[i]] ){VisitTwo(numb[i],++sig);}}return sig;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int u=i,t,w=1;while(scanf("%d",&t)==1&&t){E++;addedge(u,t,w,l++);addedgef(t,u,w,lf++);}}int ans=Kosaraju_StronglyConnectedComponent(); printf("%d\n",ans);}return 0;12.tarjan模板//自己模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int belg[maxn];//第i个节点属于belg[i]个强连通分量int stck[maxn],stop;//stck栈int instck[maxn];//第i个节点是否在栈中int scnt;//强联通分量int index;void dfs(int i){dfn[i]=lowc[i]=++index;instck[i]=1;//节点i入栈stck[++stop]=i;for(int j=p[i];j!=-1;j=G[j].next){int t=G[j].t;//更新lowc数组if(!dfn[t])//t没有遍历过{dfs(t);if(lowc[i]>lowc[t]) lowc[i]=lowc[t];}//t是i的祖先节点else if(instck[t]&&lowc[i]>dfn[t]) lowc[i]=dfn[t];}//是强连通分量的根节点if(dfn[i]==lowc[i]){scnt++;int t;do{t=stck[stop--];instck[t]=0;belg[t]=scnt;}while(t!=i);}}int tarjan(){stop=scnt=index=0;memset(dfn,0,sizeof(dfn));memset(instck,0,sizeof(instck));for(int i=1;i<=V;i++){if(!dfn[i]) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}//吉大模板邻接表版#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int stck[maxn],stop;//stck栈int pre[maxn];//int scnt;//强联通分量int cnt;//void dfs(int v)//1-V{int t,minc=lowc[v]=pre[v]=cnt++;stck[stop++]=v;for(int i=p[v];i!=-1;i=G[i].next){int pv=G[i].t;if(pre[pv]==-1) dfs(pv);if(lowc[pv]<minc) minc=lowc[pv]; }if(minc<lowc[v]){lowc[v]=minc;return ;}do{dfn[t=stck[--stop]]=scnt;lowc[t]=V;}while(t!=v);++scnt;}int tarjan(){stop=cnt=scnt=0;memset(pre,-1,sizeof(pre));for(int i=1;i<=V;i++){if(pre[i]==-1) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}二、数学1．剩余定理int mod(int c[],int b[],int n){int all_multy=1,sum=0;int i,j,x[5];for(i=0;i<n;i++)all_multy*=c[i];for(i=0;i<n;i++)x[i]=all_multy/c[i];for(i=0;i<n;i++){j=1;while((x[i]*j)%c[i]!=1)j++;x[i]*=j;}for(i=0;i<n;i++)sum+=(b[i]*x[i]);return sum%all_multy;}2．N!中质因子P的个数//对于任意质数p，n！中有（n/p+n/p^2+n/p^3+...)个质因子p。