[REVIEW] 图论基础算法

Kruskal 最小生成树 //Kruskal #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=200005; struct edge {int l,r,w;} f[mxn]; ll ans; int n,m,cnt; int father[mxn]; inline bool comp(edge x,edge y) {return x.w<y.w;} inline int find(int x) { if(x!=father[x]) father[x]=find(father[x]); return father[x]; } inline void kruskal() { int i,j; fo(i,1,m) { int t1=find(f[i].l),t2=find(f[i].r); if(t1!=t2) father[t1]=t2,cnt++,ans+=f[i].w; } } int main() { int i,j; scanf("%d%d",&n,&m); fo(i,1,n) father[i]=i; fo(i,1,m) scanf("%d%d%d",&f[i].l,&f[i].r,&f[i].w); sort(f+1,f+m+1,comp); kruskal(); if(cnt==n-1) printf("%lld\n",ans); else printf("orz\n"); return 0; }

---

带偏移量的并查集（知道节点到并查集总父亲的距离） //偏移量并查集 //NOI 2002 银河英雄传说 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=30005; int father[mxn],dis[mxn],siz[mxn]; int T; char s[10]; inline int find(int x) { if(x!=father[x]) { int fa=find(father[x]); if(father[x]!=fa) dis[x]=dis[x]+dis[father[x]]-1; father[x]=fa; } return father[x]; } inline void Union(int x,int y) { int t1=find(x),t2=find(y); father[t1]=t2; dis[t1]=siz[t2]+1; siz[t2]+=siz[t1]; siz[t1]=0; } int main() { int i,j,x,y; scanf("%d",&T); fo(i,1,30000) father[i]=i,dis[i]=siz[i]=1; while(T--) { scanf("%s",s); scanf("%d%d",&x,&y); if(s[0]=='M') Union(x,y); else { if(find(x)!=find(y)) printf("-1\n"); else printf("%d\n",abs(dis[x]-dis[y])-1); } } return 0; }

---

有向图/无向图 最短路（spfa实现） //spfa #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=100005; queue <int> q; int n,m,s,cnt; int head[mxn],dis[mxn]; struct edge {int to,d,next;} f[500005]; bool vis[mxn]; inline void add(int u,int v,int w) { f[++cnt].to=v,f[cnt].d=w,f[cnt].next=head[u],head[u]=cnt; } inline void spfa() { int i,j; fo(i,1,n) dis[i]=2147483647ll; dis[s]=0; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(i=head[u];i;i=f[i].next) { int v=f[i].to,d=f[i].d; if(dis[v]>dis[u]+d) { dis[v]=dis[u]+d; if(!vis[v]) vis[v]=1,q.push(v); } } } } int main() { int i,j,k,u,v,w; scanf("%d%d%d",&n,&m,&s); while(m--) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); } spfa(); fo(i,1,n) printf("%d ",dis[i]); return 0; }

---

拓扑排序 //top sort #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=100005; queue <int> q; int n,m,s,cnt; int head[mxn],dep[mxn],du[mxn]; struct edge {int to,next;} f[200005]; inline void add(int u,int v) { f[++cnt].to=v,f[cnt].next=head[u],head[u]=cnt; } inline void topsort() { int i,j; fo(i,1,n) if(!du[i]) dep[i]=1,q.push(i); while(!q.empty()) { int u=q.front(); q.pop(); for(i=head[u];i;i=f[i].next) { int v=f[i].to; du[v]--; dep[v]=max(dep[v],dep[u]+1); if(du[v]==0) q.push(v); } } } int main() { int i,j,k,u,v,w; scanf("%d%d",&n,&m); while(m--) { scanf("%d%d",&u,&v); add(u,v),du[v]++; } topsort(); fo(i,1,n) printf("%d\n",dep[i]); return 0; }

---

tarjan求强连通分量（NOIP 2015 信息传递） //强连通 #include<stack> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=200005; stack <int> s; int n,tim,ans=1e9; int to[mxn],low[mxn],dfn[mxn]; bool in[mxn]; inline void tarjan(int u) { dfn[u]=low[u]=++tim; in[u]=1; s.push(u); int v=to[u]; if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]); else if(in[v]) low[u]=min(low[u],dfn[v]); if(dfn[u]==low[u]) { int siz=0; do { v=s.top(); s.pop(); in[v]=0; siz++; }while(u!=v); if(siz>1) ans=min(ans,siz); } } int main() { int i,j; scanf("%d",&n); fo(i,1,n) scanf("%d",&to[i]); fo(i,1,n) if(!dfn[i]) tarjan(i); printf("%d\n",ans); return 0; }