[ Miller-Rabin Strong Probable-prime Base ] 質數測試算法保證long long範圍內正確

這本來是隨機演算法，但是已經有一些人，找出一些特定底數，保證判定結果在某些範圍內正確。

如果是unsigned long long範圍內東西記得要用long long乘long long mod long long 的模板
這裡的範例已經加在code裡了，如果不需要可以把它拿掉(zerojudge a007不拿掉會變慢)

code:

	inline long long mod_mul(long long a,long long b,long long m){
	a%=m,b%=m;
	long long y=(long long)((double)a*b/m+0.5);/* fast for m < 2^58 */
	long long r=(a*b-y*m)%m;
	return r<0?r+m:r;
	}
	template<typename T>
	inline T pow(T a,T b,T mod){//a^b%mod
	T ans=1;
	for(;b;a=mod_mul(a,a,mod),b>>=1)
	if(b&1)ans=mod_mul(ans,a,mod);
	return ans;
	}
	int sprp[3]={2,7,61};//int範圍可解
	int llsprp[7]={2,325,9375,28178,450775,9780504,1795265022};//至少unsigned long long範圍
	template<typename T>
	inline bool isprime(T n,int *sprp,int num){
	if(n==2)return 1;
	if(n<2||n%2==0)return 0;
	int t=0;
	T u=n-1;
	for(;u%2==0;++t)u>>=1;
	for(int i=0;i<num;++i){
	T a=sprp[i]%n;
	if(a==0||a==1||a==n-1)continue;
	T x=pow(a,u,n);
	if(x==1||x==n-1)continue;
	for(int j=1;j<t;++j){
	x=mod_mul(x,x,n);
	if(x==1)return 0;
	if(x==n-1)break;
	}
	if(x==n-1)continue;
	return 0;
	}
	return 1;
	}

view raw Miller-Rabin.cpp hosted with ❤ by GitHub

[ Biconnected Component ] 雙連通分量(BCC)

一張無向圖上，不會產生割點的連通分量，稱作「雙連通分量」。一張無向圖的雙連通分量們，通常會互相重疊，重疊的部分都是原圖的割點。
可以利用堆疊+tarjan算法快速地找出那些點是割點和雙連通分量
以下提供模板:

	#include<vector>
	#include<algorithm>
	#define N 1005
	std::vector<int> G[N];// 1-base
	std::vector<int> bcc[N];//存每塊雙連通分量的點
	int low[N],vis[N],Time;
	int bcc_id[N],bcc_cnt;// 1-base
	bool is_cut[N];//是否為割點，割點的bcc_id沒意義
	int st[N],top;
	void dfs(int u,int pa=-1){//u當前點，pa父親
	int v,child=0;
	low[u]=vis[u]=++Time;
	st[top++]=u;
	for(size_t i=0;i<G[u].size();++i){
	if(!vis[v=G[u][i]]){
	dfs(v,u),++child;
	low[u]=std::min(low[u],low[v]);
	if(vis[u]<=low[v]){
	is_cut[u]=1;
	bcc[++bcc_cnt].clear();
	int t;
	do{
	bcc_id[t=st[--top]]=bcc_cnt;
	bcc[bcc_cnt].push_back(t);
	}while(t!=v);
	bcc_id[u]=bcc_cnt;
	bcc[bcc_cnt].push_back(u);
	}
	}else if(vis[v]<vis[u]&&v!=pa)//反向邊
	low[u]=std::min(low[u],vis[v]);
	}
	if(pa==-1&&child<2)is_cut[u]=0;//u是dfs樹的根要特判
	}
	inline void bcc_init(int n){
	Time=bcc_cnt=top=0;
	for(int i=1;i<=n;++i){
	G[i].clear();
	vis[i]=0;
	is_cut[i]=0;
	bcc_id[i]=0;
	}
	}

view raw BC.cpp hosted with ❤ by GitHub

[ Strongly Connected Component - Tarjan & Kosaraju ] 強連通分量的兩種做法(dfs)

一張有向圖，找到所有的 Strongly Connected Component ；亦可進一步收縮所有的 SCC 、收縮所有的環，讓原圖變成 DAG 。

方法1-Tarjan法
跟BCC差不多，直接提供模板:

	#include<vector>
	#include<algorithm>
	#define N 50005
	std::vector<int> s[N];
	int low[N],v[N]={0},Time=0,ans=0,cnt=0;
	int st[N],top=0,contract[N];
	bool instack[N]={0};
	void dfs(int x){
	low[x]=v[x]=++Time;
	st[top++]=x;
	instack[x]=1;
	for(int i=0,r;i<(int)s[x].size();++i){
	if(!v[r=s[x][i]])dfs(r);
	if(instack[r])low[x]=std::min(low[x],low[r]);
	}
	if(v[x]==low[x]){
	int u;
	do{
	instack[u=st[--top]]=0;
	contract[u]=cnt;/*每個點所在的SCC*/
	}while(u!=x);
	++cnt;
	}
	}

view raw SCC_tarjan.cpp hosted with ❤ by GitHub

方法2-Kosaraju
對圖做一次DFS，求他的時間戳，再把圖反向，逆著時間戳進行第二次DFS，所遍歷的點就會是同一個SCC，記得不要走重複的點
以下提供模板:

	#include<vector>
	#include<algorithm>
	#define N 1000005
	std::vector<int >s[N],g[N];/*g是反向圖，要先做好*/
	bool v[N]={0};
	int st[N],top=0,contract[N]={0};
	void dfs(int x){
	v[x]=1;
	for(int i=0;i<(int)s[x].size();++i){
	if(!v[s[x][i]])dfs(s[x][i]);
	}
	st[top++]=x;
	}
	void dfs2(int x,int k){
	if(contract[x])return;
	contract[x]=k;/*x屬於第k個contract*/
	for(int i=0;i<(int)g[x].size();++i){
	dfs2(g[x][i],k);
	}
	}

view raw SCC_DFS.cpp hosted with ❤ by GitHub

用法:

	int n,m;
	int a,b;
	int main(){
	scanf("%d%d",&n,&m);/*n個點m條邊*/
	while(m--){
	scanf("%d%d",&a,&b);
	s[a].push_back(b);
	g[b].push_back(a);/*反向圖*/
	}
	for(int i=0;i<n;++i){
	if(!v[i])dfs(i);/*第一次DFS*/
	}
	for(int i=0;i<top;++i)printf("%d ",st[i]);puts("");
	for(int i=top-1,t=0;i>=0;--i){/*反著處理*/
	if(!contract[st[i]])dfs2(st[i],++t);
	}
	for(int i=0;i<n;i++)printf("%d ",contract[i]);
	return 0;
	}

view raw SCC_DFS_use.cpp hosted with ❤ by GitHub

[ Bridge & Bridge-connected Component ] 橋和橋連通分量(BCC)

只要從一張無向圖上移除了橋，就會讓這張圖分離成更多部分，呈現不連通的狀態。
注意！必須要考慮重邊的問題:

1. 對於有向圖的強連通分量，重邊是沒有影響的，因為強連通只要求任意兩點可以互相連通
2. 對於無向圖的點雙連通分量，重邊也是沒有影響的，因為點雙連通要求是任意兩點之間至少存在兩條點不重複的路徑，對邊的重複並沒有要求
3. 對於無向圖的邊雙連通分量，重邊就有影響了，因為邊雙連通要求任意兩點之間至少存在兩條邊不重複的路徑

這裡提供模板:

	#include<vector>
	#include<algorithm>
	#define N 1005
	struct edge{
	int u,v;
	bool is_bridge;
	edge(int u=0,int v=0):u(u),v(v),is_bridge(0){}
	};
	std::vector<edge> E;
	std::vector<int> G[N];// 1-base
	int low[N],vis[N],Time,bridge_cnt;
	inline void add_edge(int u,int v){
	G[u].push_back(E.size());
	E.push_back(edge(u,v));
	G[v].push_back(E.size());
	E.push_back(edge(v,u));
	}
	void dfs(int u,int re=-1){//u當前點，re為u連接前一個點的邊
	int v;
	low[u]=vis[u]=++Time;
	st[top++]=u;
	for(size_t i=0;i<G[u].size();++i){
	int e=G[u][i];v=E[e].v;
	if(!vis[v]){
	dfs(v,e^1);//e^1反向邊
	low[u]=std::min(low[u],low[v]);
	if(vis[u]<low[v]){
	E[e].is_bridge=E[e^1].is_bridge=1;
	++bridge_cnt;
	}
	}else if(vis[v]<vis[u]&&e!=re)
	low[u]=std::min(low[u],vis[v]);
	}
	}

view raw bridge.cpp hosted with ❤ by GitHub

一張無向圖上，不會產生橋的連通分量，稱作橋連通分量，或是橋雙連通分量
這裡提供模板，code跟橋差不多，只是需要用堆疊去記錄當前節點而已:

	#include<vector>
	#include<algorithm>
	#define N 1005
	struct edge{
	int u,v;
	bool is_bridge;
	edge(int u=0,int v=0):u(u),v(v),is_bridge(0){}
	};
	std::vector<edge> E;
	std::vector<int> G[N];// 1-base
	int low[N],vis[N],Time;
	int bcc_id[N],bridge_cnt,bcc_cnt;// 1-base
	int st[N],top;//BCC用
	inline void add_edge(int u,int v){
	G[u].push_back(E.size());
	E.push_back(edge(u,v));
	G[v].push_back(E.size());
	E.push_back(edge(v,u));
	}
	void dfs(int u,int re=-1){//u當前點，re為u連接前一個點的邊
	int v;
	low[u]=vis[u]=++Time;
	st[top++]=u;
	for(size_t i=0;i<G[u].size();++i){
	int e=G[u][i];v=E[e].v;
	if(!vis[v]){
	dfs(v,e^1);//e^1反向邊
	low[u]=std::min(low[u],low[v]);
	if(vis[u]<low[v]){
	E[e].is_bridge=E[e^1].is_bridge=1;
	++bridge_cnt;
	}
	}else if(vis[v]<vis[u]&&e!=re)
	low[u]=std::min(low[u],vis[v]);
	}
	if(vis[u]==low[u]){//處理BCC
	++bcc_cnt;// 1-base
	do bcc_id[v=st[--top]]=bcc_cnt;//每個點所在的BCC
	while(v!=u);
	}
	}
	inline void bcc_init(int n){
	Time=bcc_cnt=bridge_cnt=top=0;
	E.clear();
	for(int i=1;i<=n;++i){
	G[i].clear();
	vis[i]=0;
	bcc_id[i]=0;
	}
	}

view raw BCC.cpp hosted with ❤ by GitHub

[ Articulation Vertex ] 割點

關節點(割點)是讓一張無向圖維持連通，不可或缺的點。只要從一張無向圖上移除了關節點（以及與之相連的邊），就會讓這張圖分離成更多部分，呈現不連通的狀態。
存在一種線性算法找出一張圖所有的割點，一個dfs就能解決了

以下提供模板:

	#include<vector>
	#include<algorithm>
	#define N 50005
	std::vector<int> s[N];
	int low[N],v[N]={0},Time=0,ans=0;
	void dfs(int x,int p){/*x當前點，p父親*/
	int i,r,is=0,add=0;
	low[x]=v[x]=++Time;
	for(i=0;i<(int)s[x].size();++i){
	if(!v[r=s[x][i]]){
	dfs(r,x),++add;
	low[x]=std::min(low[x],low[r]);
	if(v[x]<=low[r])is=1;
	}
	if(r!=p)low[x]=std::min(low[x],v[r]);
	}/*傳回有幾個割點*/
	if(is)++ans;
	if(x==p&&add<2)--ans;/*x是dfs樹的根要特判*/
	}

view raw Articulation Vertex.cpp hosted with ❤ by GitHub