圖專題
并查集倒庵，尋找父節(jié)點(diǎn)券勺，合并模板
/*
這題有個(gè)小坑挑围，當(dāng)然也不算是坑赌厅，就是焕刮，看起來是求并查集的沒錯(cuò)注益，但是額外附加了一個(gè)條件碴巾，單個(gè)端點(diǎn)只接收一次消息，所以丑搔，不能有環(huán)出現(xiàn)厦瓢，排除也很簡(jiǎn)單，根據(jù)樹的邊數(shù)為n-1定則啤月，而且要所有端點(diǎn)必須為同一集合煮仇，那么M必須等于N-1，否則谎仲，
所有端點(diǎn)無(wú)法連通浙垫，或出現(xiàn)環(huán)，so~題目就簡(jiǎn)單啦~~
*/
#include <iostream>
using namespace std;
//通信系統(tǒng)强重，要求所有結(jié)點(diǎn)都能收到發(fā)端消息且不重復(fù)
int father[1000];
int findFather(int a){
int x=a;
while(x!=father[x]){
x=father[x];
}
while(a!=father[a]){
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
void init(int n){
for(int i=1;i<=n;i++){
father[i]=i;
}
}
void Union(int a,int b){
int A=findFather(a);
int B=findFather(b);
if(A!=B){
father[A]=B;
}
}
int main()
{
int n,k,a,b;
while(cin>>n>>k){
if(n==0) break;
init(n);
for(int i=0;i<k;i++){
cin>>a>>b;
Union(a,b);
}
int ans=0;
for(int i=1;i<=n;i++){
if(father[i]==i)
ans++;
}
//邊只能有n-1條時(shí)才不會(huì)有環(huán)＝食省！
if(ans==1&&k==n-1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
圖的遍歷DFS鄰接矩陣和鄰接表法
//給定一個(gè)無(wú)向圖和所有邊间景，判斷這個(gè)圖是否所有頂點(diǎn)都是聯(lián)通的
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1010;
bool G[maxn][maxn];
bool flag[maxn]={false};
int n;
//n是點(diǎn)數(shù)佃声，m是邊數(shù)
void DFS(int x){
flag[x]=true;
for(int i=1;i<=n;i++){
//由于是無(wú)向邊true表示可達(dá)
if(flag[i]==false&&G[x][i]==true){
G[x][i]=false;
G[i][x]=false;
//上面這個(gè)操作是為了提前清除已經(jīng)訪問邊，這樣就可以 不用下一組初始化
DFS(i);
}
}
}
int main(){
int m,d1,d2;
while(cin>>n>>m){
if(n==0) break;
for(int i=0;i<m;i++){
cin>>d1>>d2;
if(G[d1][d2]==false)
G[d1][d2]=G[d2][d1]=true;
}
int number=0;
memset(flag,0,sizeof(flag));
for(int i=1;i<=n;i++){
if(flag[i]==false){
number++;
DFS(i);
}
}
if(number==1){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}
//鄰接矩陣法倘要，其實(shí)就要最后的連通塊只有一個(gè)圾亏，有點(diǎn)類似并查集！封拧！
//鄰接表法
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=1010;
vector<int> Adj[maxn];
bool flag[maxn]={false};
int n;
void DFS(int x){
flag[x]=true;
for(int i=0;i<Adj[x].size();i++){
int u=Adj[x][i];
//x的后繼點(diǎn)Ｖ揪椤！
if(flag[u]==false){
DFS(u);
}
}
//清空泽西，這樣不用初始化為空
Adj[x].clear();
}
using namespace std;
int main()
{
int m,d1,d2;
while(cin>>n>>m)
{
if(n==0)
break;
for(int i=0;i<m;i++){
cin>>d1>>d2;
Adj[d1].push_back(d2);
Adj[d2].push_back(d1);
}
int number=0;
memset(flag,0,sizeof(flag));
for(int i=1;i<=n;i++){
if(flag[i]==false){
number++;
DFS(i);
}
}
if(number==1) printf("YES\n");
else printf("NO\n");
}
return 0;
}
迪杰特斯拉求最短路徑長(zhǎng)度+從某點(diǎn)到另一點(diǎn)的路徑
6 8 0
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3
0 1 5 3 4 6
//迪杰特斯拉最短路勁
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXV=1000; //最大頂點(diǎn)數(shù)
const int INF=1000000000; //設(shè)置一個(gè)很大值表示不可達(dá)
int n,m,s,G[MAXV][MAXV]; //n為頂點(diǎn)數(shù)曹铃，m為邊數(shù)，s為起點(diǎn)
int d[MAXV]; //起點(diǎn)到各點(diǎn)的最短路徑長(zhǎng)度
int pre[MAXV]; //prev【v】表示從起點(diǎn)到頂點(diǎn)v的最短路徑上v的前一個(gè)頂點(diǎn)
bool vis[MAXV]={false}; //標(biāo)記數(shù)組
void Dijkstra(int s){
fill(d,d+MAXV,INF); //s到所有點(diǎn)先設(shè)置成不可達(dá)
d[s]=0; //這個(gè)也很關(guān)鍵捧杉，s一開始到自己為0
for(int i=0;i<n;i++){
int u=-1,MIN=INF; //找到使d[u]最小的u,MIn存放最小的d[u]
for(int j=0;j<n;j++){
//第一輪自由一個(gè)d[s]=0,之后每輪d[u]都是更新的Ｉ录！
if(vis[j]==false&&d[j]<MIN){
u=j;
MIN=d[j];
}
}
if(u==-1) return;
//找不到小于INF的d[u]說明剩下的頂點(diǎn)和起點(diǎn)s不連通
vis[u]=true;
//找到了標(biāo)記成已訪問
//從u出發(fā)能到達(dá)的下一個(gè)點(diǎn)味抖，這樣每次相當(dāng)于都知道了下一輪要訪問的點(diǎn)的距離
for(int v=0;v<n;v++){
//如果v未訪問&&u能到達(dá)v&&以u(píng)為中介點(diǎn)评甜，可以使d[v]更優(yōu)
if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
//優(yōu)化d[v]
pre[v]=u;
//記錄前驅(qū)頂點(diǎn)是u
}
}
}
}
//如何使用遞歸，根據(jù)前驅(qū)頂點(diǎn)仔涩，求最短路徑
void DFS(int s,int v){
//s為起點(diǎn)編號(hào)忍坷，v為當(dāng)前訪問的頂點(diǎn)編號(hào)，要從重點(diǎn)開始遞歸，這樣才能從頭輸出
if(v==s){
//遞歸重點(diǎn)佩研，就是達(dá)到起點(diǎn)
printf("%d\n",s);
return;
}
DFS(s,pre[v]); //遞歸訪問v的前驅(qū)頂點(diǎn)pre[v]
printf("%d\n",v); //從最深return回來之后再輸出每一層
}
int main()
{
int u,v,w;
cin>>n>>m>>s;
//頂點(diǎn)個(gè)數(shù)柑肴，邊數(shù)，起點(diǎn)編號(hào)
fill(G[0],G[0]+MAXV*MAXV,INF);
//對(duì)于矩陣如何初始化韧骗，學(xué)到了
for(int i=0;i<m;i++){
cin>>u>>v>>w;
G[u][v]=w;
//輸入u嘉抒，v以及u->v的邊權(quán)零聚，有向圖
}
Dijkstra(s);
//直接算法入口
for(int i=0;i<n;i++){
//輸出s到所有頂點(diǎn)的最短距離
printf("%d ",d[i]);
}
cout<<endl;
DFS(0,3);
return 0;
}
優(yōu)先隊(duì)列實(shí)現(xiàn)地杰斯特拉
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=60;
const int INF=0x3fffffff;
int G[maxn][maxn],n,d[maxn];
bool vis[maxn]={false};
struct Node{
int v,dis;
//這是有點(diǎn)隊(duì)列所需要的Ｅ郾！
bool operator<(const Node &a)const{
return dis>a.dis;
}
//結(jié)構(gòu)定義
Node(int x,int y){
v=x;
dis=y;
}
};
void Dijkstra(int s){
fill(d,d+maxn,INF);
d[s]=0;
//使用優(yōu)先隊(duì)列查找未訪問的距離最短結(jié)點(diǎn)
priority_queue<Node> q;
q.push(Node(s,d[s]));
for(int i=0;i<n;i++){
if(q.empty()==true) return;
while(vis[q.top().v]==true){
q.pop();
if(q.empty()==true) return;
}
int u=q.top().v;
q.pop();
for(int v=0;v<n;v++){
if(G[u][v]!=0&&vis[v]==false&&d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
q.push(Node(v,d[v]));
}
}
}
}
int main()
{
int s;
while(cin>>n){
cin>>s;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>G[i][j];
}
}
Dijkstra(s);
for(int i=0;i<n;i++){
if(i!=s){
if(d[i]==INF)
printf("-1 ");
else printf("%d ",d[i]);
}
}
printf("\n");
}
return 0;
}
prim最小生成樹算法
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=110;
const int INF=0x3fffffff;
int G[maxn][maxn],d[maxn];
int n;
bool vis[maxn];
int prim()
{
fill(d,d+maxn,INF);
memset(vis,0,sizeof(vis));
d[1]=0;
int ans=0;
for(int i=0;i<n;i++)
{
int min=INF,u=-1;
for(int j=1;j<=n;++j)
{
if(d[j]<min&&vis[j]==false)
{
u=j;
min=d[j];
}
}
//終于知道-1的作用隶症，表示存在沒有聯(lián)通的地方Ｕ！！
if(u==-1)
return -1;
vis[u]=true;
ans+=d[u];
for(int v=1;v<=n;++v)
{
if(vis[v]==false&&G[u][v]!=INF&&G[u][v]<d[v])
{
d[v]=G[u][v];
}
}
}
return ans;
}
int main()
{
int w,u,v;
while(~scanf("%d",&n))
{
if(n==0)
break;
fill(G[0],G[0]+maxn*maxn,INF);
for(int i=0;i<n*(n-1)/2;++i)
{
scanf("%d %d %d",&u,&v,&w);
G[u][v]=G[v][u]=w;
}
int ans=prim();
printf("%d\n",ans);
}
return 0;
}
并查集+最小生成樹
#include <iostream>
#include <algorithm>
using namespace std;
#define N 101
int Tree[N];
//關(guān)鍵算法蚂会，找到爸爸節(jié)結(jié)點(diǎn)的標(biāo)號(hào)
int findRoot(int x){
//查找代表集合的樹的根節(jié)點(diǎn)淋样，分成兩個(gè)集合，以此來判斷是否要合并兩點(diǎn)到一個(gè)集合
if(Tree[x]==-1){
return x;
}else{
//當(dāng)Tree[x]=1時(shí)胁住，表示x爸爸是1趁猴，Tree[1]=-1,return Tree[x]=1是一個(gè)整體！彪见！
int tmp=findRoot(Tree[x]);
//找x的爸爸儡司，遞歸
Tree[x]=tmp;
//tmp確實(shí)是x的爸爸，爸爸存了
return tmp;
}
}
struct Edge{
//邊要有結(jié)構(gòu)體余指，來進(jìn)行排序
int a,b;//頂點(diǎn)編號(hào)
int cost;
//重載小于運(yùn)算符很關(guān)鍵２度！
bool operator < (const Edge &A) const{
return cost<A.cost;
}edge[6000];
int main(){
int n;
while(cin>>n){
for(int i=1;i<=n*(n-1)/2;i++){
cin>>edge[i].a>>edge[i].b>>edge[i].cost;
}
sort(edge+1,edge+1+n*(n-1)/2);
for(int i=1;i<=n;i++){
Tree[i]=-1;
//初始所有邊都處于孤立集合
}
int ans=0;
for(int i=1;i<=n*(n-1)/2;i++){
int a=findRoot(edge[i].a);
int b=findRoot(edge[i].b);
//查找兩個(gè)頂點(diǎn)的集合信息
if(a!=b){
Tree[b]=a;
//合并兩個(gè)集合酵镜，加入了一個(gè)邊
cout<<a<<" "<<b<<" "<<edge[i].cost<<endl;
ans=ans+edge[i].cost;
}
}
cout<<ans;
}
return 0;
}
}
克魯斯卡爾最小生成樹
6 10
0 1 4
0 4 1
0 5 2
1 2 1
1 5 3
2 3 6
2 5 5
3 4 5
3 5 4
4 5 3
11
//克魯斯卡爾最小生成樹算法
#include <iostream>
#include <32/bits/stdc++.h>
using namespace std;
const int MAXV=110;
const int MAXE=10010;
struct edge{
int u,v; //邊的兩個(gè)端點(diǎn)編號(hào)
int cost; //邊權(quán)
}E[MAXE];
bool cmp(edge a,edge b){
return a.cost<b.cost;
}
//并查集部分
int father[MAXV]; //并查集數(shù)組
int findFather(int x){
//并查集查詢函數(shù)
int a=x;
while(x!=father[x]){
x=father[x];
}
//路徑要鎖碉碉，直接得到每個(gè)點(diǎn)的爸爸
while(a!=father[a]){
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
//n為頂點(diǎn)個(gè)數(shù)，m為圖的邊數(shù)
int kruskal(int n,int m){
//ans為所求邊權(quán)和淮韭，Num_Edge為當(dāng)前生成樹的邊數(shù)
int ans=0,Num_Edge=0;
for(int i=0;i<n;i++){
father[i]=i; //并查集初始化
}
sort(E,E+m,cmp); //所有邊按權(quán)值大小排序
for(int i=0;i<m;i++){
cout<<E[i].v<<" "<<E[i].u<<" "<<E[i].cost<<endl;
}
cout<<"路徑："<<endl;
for(int i=0;i<m;i++){
//枚舉所有邊
int faU=findFather(E[i].u); //查詢測(cè)試邊兩個(gè)端點(diǎn)所在集合根結(jié)點(diǎn)
int faV=findFather(E[i].v);
//這就是合并了
if(faU!=faV){
//只有不在同一個(gè)集合才可以合并
father[faU]=faV;
ans+=E[i].cost;
cout<<E[i].v<<"->"<<E[i].u<<endl;
Num_Edge++; //當(dāng)前生成樹邊數(shù)加1
if(Num_Edge==n-1) break;
//邊數(shù)等于頂點(diǎn)數(shù)減一時(shí)結(jié)束算法
}
}
if(Num_Edge!=n-1) return -1; //無(wú)法連通時(shí)返回-1
else return ans; //返回最小生成樹的邊權(quán)之和
}
int main()
{
int n,m;
cin>>n>>m; //頂點(diǎn)數(shù)和邊數(shù)
for(int i=0;i<m;i++){
cin>>E[i].u>>E[i].v>>E[i].cost;
}
int ans=kruskal(n,m);
cout << ans<< endl;
return 0;
}
