图论题目集一（代码 注解）

目录

题目一： 

题目二：

题目三：

题目四：

题目五：

题目六：

题目七：

题目一： 

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int g[15][15], vis[15] = { 0 };
int n, m;
queue<int> q;
void dfs(int k)//深度
{cout << k << " ";vis[k] = 1;for (int i = 0; i < n; i++){if (i == k)continue;if (vis[i] == 0 && g[k][i]){dfs(i);}}return;
}
void bfs(int k)//广度
{q.push(k);while (!q.empty()){k = q.front();q.pop();if(vis[k]==0){cout<<k<<" ";vis[k]=1;}for (int i = 0; i < n; i++){if (vis[i] == 0 && g[k][i] == 1){q.push(i);}}}return;
}
int main()
{cin >> n >> m;for (int i = 1; i <= m; i++)//构建邻接矩阵{int x, y;cin >> x >> y;g[x][y] = 1, g[y][x] = 1;}for (int i = 0; i < n; i++)//深度{if (vis[i] == 0){cout << "{ ";dfs(i);cout << "}" << endl;}}memset(vis, 0, sizeof(vis));for (int i = 0; i < n; i++)//广度{if(vis[i]==0){cout << "{ ";bfs(i);cout << "}" << endl;}}
}

 题目二：

#include<iostream>
#include<algorithm>
using namespace std;
int g[10005][10005];
float n, k;
typedef struct node
{int data;int w = 0;
}node;
void warshall()//传递闭包
{for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){if (g[i][k] && g[k][j])//连通{if (i == j)continue;if (g[i][j] == 0 || g[i][j] > g[i][k] + g[k][j])//没有直接连通或者新通路距离小于之前通路g[i][j] = g[i][k] + g[k][j];}}
}
bool cmp(node a, node b)
{return a.w < b.w;
}
int main()
{cin >> n >> k;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)g[i][j] = 0;for (int i = 0; i < k; i++)//无向图，初始距离都为1{int v1, v2;cin >> v1 >> v2;g[v1][v2] = 1;g[v2][v1] = 1;}warshall();/*for (int i = 1; i <= n; i++)//输出邻接矩阵{for (int j = 1; j <= n; j++)cout << g[i][j] << " ";cout << endl;}*/float ans[10005] ;for (int i = 1; i <= n; i++){ans[i] = 0;for (int j = 1; j <= n; j++){if (i == j)ans[i]++;if (g[i][j]>0 && g[i][j] <= 6)//符合条件ans[i]++;}}for (int i = 1; i <= n; i++)printf("%d:% .2f%%\n", i, ans[i] / n * 100);
}

题目三：

#include<iostream>
using namespace std;
int g[1010][1010];
int n,m,s;
int vis[1010];
int path[1010];
int cnt=0;
void dfs(int k)//深度
{//cout<<k<<" ";path[cnt++]=k;//记录去的路径vis[k]=1;for(int i=0;i<=n;i++){if(i==k)continue;if(vis[i]==0&&g[k][i]==1){dfs(i);path[cnt++]=k;//记录回的路径}}return ;
}
int main()
{cin>>n>>m>>s;for(int i=1;i<=m;i++)//构建邻接矩阵{int x,y;cin>>x>>y;g[x][y]=g[y][x]=1;}dfs(s);int flag=1;//标记是否可以遍历完所有for(int i=1;i<=n;i++)//查询是否遍历完所有{if(vis[i]==0){flag=0;break;}}if(flag==1)//输出序列{for(int i=0;i<cnt;i++){cout<<path[i];if(i!=cnt-1)cout<<" ";}}else{for(int i=0;i<cnt;i++)cout<<path[i]<<" ";cout<<0;}
}

题目四：

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
struct  node
{ll v, w;bool operator <(const node& y) const//重载一个<,用于优先队列排序{return w > y.w;//小到大}
};
int n, m, t;
priority_queue<node>q;
vector<node> e[N];
ll dis[N], vis[N];
void Dij(int t)
{dis[t] = 0;//从t号点出发，表示从t到t距离为0q.push({ t,dis[t] });//t号点以及到t的距离入队while (q.size()){int u = q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] = 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v = i.v, w = i.w;//取其相连的点及权值if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新{dis[v] = dis[u] + w;q.push({ v,dis[v] });//v点以及到v的距离}}}}
int main()
{cin >> n >> m;for (int i = 1; i <= m; i++){int x, y, w=1;cin >> x >> y;e[x].push_back({ y,w });//存入以x出发到y，权值为we[y].push_back({ x,w });//存入以x出发到y，权值为w}int N;cin >> N;while (N--){cin >> t;float ans = 0,sum=0;memset(dis, 0x3f3f3f, sizeof(dis));memset(vis, 0, sizeof(vis));Dij(t);//从t点出发for (int i = 1; i <= n; i++){sum += dis[i];//求和}//cout << sum;ans = (n - 1) /sum;printf("Cc(%d)=%.2f\n", t, ans);}
}

题目五：

#include<iostream>//并查集
using namespace std;
int fa[204], mp[102][102];
int find(int x)//查找
{if(fa[x]==x)  return x;return fa[x]=find(fa[x]);
}
void Merge(int x, int y)//合并
{int a=find(x), b=find(y);if(a==b) return;else fa[a]=fa[b];
}
int main()
{int n, m, k;cin>>n>>m>>k;int a, b, c;for(int i=1;i<=n;i++)//初始化fa[i]=i;for(int i=0; i<m; i++){cin>>a>>b>>c;mp[a][b]=c,mp[b][a]=c;if(c==1)//为朋友则合并，因为朋友的朋友也是朋友Merge(a, b);}for(int i=0; i<k; i++){cin>>a>>b;if(mp[a][b]==1) cout<<"No problem"<<endl;else if(mp[a][b]==-1)//是敌对关系{if(find(a)==find(b))    cout<<"OK but..."<<endl;//但是有相同的朋友，即在一个集合内else cout<<"No way"<<endl;}else cout<<"OK"<<endl;}return 0;
}

题目六：

#include<iostream>
using namespace std;
int n, m, mp[520][520], f[520];
void init() //初始化
{for (int i = 0; i < n; i++)f[i] = i;
}
int find(int x) //查询
{if (x == f[x]) return x;return f[x] = find(f[x]);
}
void merge(int x, int y)//合并 
{int xx = find(x);int yy = find(y);if (xx != yy) f[xx] = yy;return;
}
int sum()//统计连通块个数
{int cnt = 0;for (int i = 0; i < n; i++) //统计连通块个数 {if (i == find(i)) cnt++;}return cnt;
}
int main() 
{int a, b, k, x, cnt = 0, cnt2, flag = 0;cin >> n >> m;init();while (m--) {cin >> a >> b;mp[a][b] = 1;mp[b][a] = 1;merge(a, b);}cin >> k;cnt = sum();if (k == n) flag = 1; //要输出Game Over; while (k--) {cin >> x;init();cnt2 = 0;  //x去掉后的连通区域个数 for (int i = 0; i < n; i++) mp[x][i] = mp[i][x] = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++){if (mp[i][j]) merge(i, j);}}cnt2 = sum();if (cnt2 < cnt + 2) cout << "City " << x << " is lost." << endl;else cout << "Red Alert: City " << x << " is lost!" << endl;//1、去掉i点后，一个连通块至少被分为两个，增加了一个cnt = cnt2;                                                 //2、去掉i点后，再次统计cnt2时，就会把去掉的点i也加上，所以要大于cnt+1}if (flag) cout << "Game Over." << endl;
}

题目七：

#include<iostream>
#include<queue>
using namespace std;
int n, id, fa, ma, k;
int f[10100], peo[10100], avgs[10100], avga[10100],st[10100];
struct node
{int a, b;
}e[10100];
struct family
{int id, peo, avgs, avga;bool operator<(const family& x)const{if (x.peo * avga == peo * x.avga)//人均相等,则升序排序return id > x.id;return x.peo * avga < peo * x.avga;//人均多的在前}
};
int find(int x)//查找
{if (f[x] == x) return x;return f[x] = find(f[x]);
}
void meger(int x, int y)//合并
{x = find(x), y = find(y);if (x != y){f[max(x, y)] = min(x, y);//小号id的设为父亲peo[min(x, y)] += peo[max(x, y)];//家庭人数加到小号idavgs[min(x, y)] += avgs[max(x, y)];//房屋数量加到小号idavga[min(x, y)] += avga[max(x, y)];//服务面积加到小号面积}
}
int main()
{for (int i = 0; i < 10100; i++) f[i] = i, peo[i] = 1;//初始化，每个父亲节点是自己，自己家庭都有一个自己cin >> n;int count = 0;for (int i = 1; i <= n; i++){cin >> id >> fa >> ma >> k;if (fa != -1) e[count++] = { id,fa };//存关系if (ma != -1) e[count++] = { id,ma };//存关系st[id] = 1;//存在这个人int kid;for (int j = 1; j <= k; j++){cin >> kid;e[count++] = { id,kid };//存关系}cin >> avgs[id] >> avga[id];}for (int i = 0; i < count; i++)//合并家庭{int a = e[i].a, b = e[i].b;st[a] = st[b] = 1;meger(a, b);//合并二者为一个家庭}priority_queue<family>ans;//优先队列for (int i = 0; i < 10100; i++){if (st[i] && f[i] == i)//这个人存在且父亲节点是自己ans.push({ i,peo[i],avgs[i],avga[i] });}//count << st[8888] << f[8888];cout << ans.size() << endl;while (!ans.empty()){family t = ans.top();ans.pop();printf("%04d %d %.3lf %.3lf\n", t.id, t.peo, (double)t.avgs / t.peo, (double)t.avga / t.peo);}
}