王道机试指南图论
例题11.1畅通工程（浙江大学上机）
#include<cstdio>
#include<iostream>
using namespace std;
int father[1000];
void initial(int n){
for(int i = 0; i <= n; i++){
father[i] = i;
}
}
int find(int x){
if(x == father[x]) return x;
else{
int f = find(father[x]);
father[x] = f;
return f;
}
}
void union0(int x, int y){
x = find(x);
y = find(y);
if(x != y){
father[x] = y;
}
}
int main(){
int n, m;
while(cin >> n && n != 0){
cin >> m;
initial(n);
int num = -1;//用来记录有多少个道路
for(int i = 0; i < m; i++){
int ta, tb;
cin >> ta >> tb;
union0(ta, tb);
}
for(int i = 1; i <= n; i++){
if(find(i) == i){
num++;
}
}
cout << num << endl;
}
return 0;
}
例题11.2连通图（吉林大学复试）
#include<iostream>
#include<cstdio>
using namespace std;
int father[1000];
void initial(int n){
for(int i = 0; i < n; i++){
father[i] = i;
}
}
int find(int x){
if(x == father[x]) return x;
else{
int f = find(father[x]);
father[x] = f;
return f;
}
}
void union0(int x, int y){
x = find(x);
y = find(y);
if(x != y){
father[x] = y;
}
}
int main(){
int n, m;
while(cin >> n && n != 0){
cin >> m;
initial(n);
for(int i = 0; i < m; i++){
int ta, tb;
cin >> ta >> tb;
union0(ta, tb);
}
int ans = 0;
for(int i = 0; i < n; i++){
if(i == find(i)) ans++;
}
if(ans > 1) cout << "NO" <<endl;
else cout << "YES" << endl;
}
return 0;
}
例题11.3 Is it a tree？（北京大学复试上机）
#include<iostream>
#include<cstdio>
using namespace std;
int father[10000];
int indegree[10000];
bool visit[10000];
void initial(int n){
for(int i = 0; i < n; i++){
father[i] = i;
indegree[i] = 0;
visit[i] = false;
}
}
int findfather(int x){
if(x == father[x]) return x;
else{
int f = findfather(father[x]);
father[x] = f;
return f;
}
}
void union0(int x, int y){
x = findfather(x);
y = findfather(y);
if(x != y) father[x] = y;
}
bool istree(){
bool flag = true;
int component = 0;
int root = 0;
for(int i = 0; i < 10000; i++){
if(!visit[i]) continue;
if(father[i] == i) component++;
if(indegree[i] == 0){
root++;
}else if(indegree[i] > 1){
flag = false;
}
}
if(component != 1 || root != 1) flag = false;
if(component == 0 && root == 0) flag = true;
return flag;
}
int main(){
int x, y;
int casenum = 0;
initial(10000);
while(cin >> x >> y &&(x != -1 && y != -1)){
if(x == 0 && y == 0){
if(istree()) cout << "Case " << ++casenum << " is a tree." << endl;
else cout << "Case " << ++casenum << " is not a tree." << endl;
initial(10000);
}
else{
union0(x, y);
indegree[y]++;
visit[x] = true;
visit[y] = true;
}
}
return 0;
}
习题11.4找出直系亲属（浙江大学上机）
#include<cstdio>
#include<iostream>
#include<string>
#include<cctype>
using namespace std;
int son[30] = {0};
int num;
int relnum(int a, int b){//判断b是否为a的后代。如果是，返回辈分差，不是，返回0
int now = a;//表示当前遍历的结点
while(now != 0){//一直循环a到没有儿子
if(now == b){//表示a的后代中找到了b，返回辈分差
return num;
}
num++;
now = son[now];
}
return 0;//没有儿子跳出循环，返回0
}
void print(int a, int b){//根据辈分差进行输出
num = 0;
int tnum1 = relnum(a, b);//记录ab辈分差差（a的辈分大于b）
num = 0;
int tnum2 = relnum(b, a);
if(tnum1 == 0 && tnum2 == 0){
cout << "-";
}else if(tnum1 != 0 && tnum2 == 0){//b是a后代
for(int i = 2; i < tnum1; i++) cout << "great-";//tnum为2的时候输出一个great
if(tnum1 == 1) cout << "parent";
if(tnum1 > 1) cout << "grandparent";
}else if(tnum2 != 0 && tnum1 == 0){
for(int i = 2; i < tnum2; i++) cout << "great-";//tnum为2的时候输出一个great
if(tnum2 == 1) cout << "child";
if(tnum2 > 1) cout << "grandchild";
}
}
int main(){
int n, m;
while(cin >> n >> m){
string s;
for(int i = 0; i < n; i++){//记录每个人的儿子
cin >> s;
if(isalpha(s[1])) son[s[1]-'A'+1] = s[0]-'A'+1;
if(isalpha(s[2])) son[s[2]-'A'+1] = s[0]-'A'+1;
}
for(int i = 0; i < m; i++){//用于测试
cin >> s;
print(s[0]-'A'+1, s[1]-'A'+1);
cout << endl;
}
}
return 0;
}
习题11.2第一题（上海交通大学复试）
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
int father[1000000];
int ans = 0;//用来记录联通分支个数
void initial(){//用于初始化并查集数组
for(int i = 0; i < 1000000; i++){
father[i] = -1;
}
}
int findfather(int x){//用于查找
if(father[x] == -1) return x;
else{
int f = findfather(father[x]);
father[x] = f;
return f;
}
}
void union0(int a, int b){//用于合并
int fa = findfather(a);
int fb = findfather(b);
if(fa != fb){
father[fa] = fb;
}
}
int main(){
int i, j;
set<int> st;//用来统计最大的数是多大
initial();
while(cin >> i >> j){
st.insert(i);
st.insert(j);
union0(i, j);
}
int ans = 0;
for(auto it = st.begin(); it != st.end(); it++){
if(father[*it] == -1) ans++;
}
cout << ans << endl;
return 0;
}
例题11.4 还是畅通工程(浙江大学)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 5000;
int father[100];
struct edge{//定义边
int u, v;//连接边的两个顶点
int cost;//边的权重
}e[MAXN];
bool cmp1(edge a, edge b){//排序的比较函数
return a.cost < b.cost;
}
int findroot(int x){
if(father[x] == x) return x;
else{
int f = findroot(father[x]);
father[x] = f;
return f;
}
}
int kruskal(int n, int m){
int ans = 0, num_edge = 0;
for(int i = 0; i < n; i++) father[i] = i;//初始化并查集
sort(e, e + m, cmp1);
for(int i = 0; i < m; i++){
int fu = findroot(e[i].u);
int fv = findroot(e[i].v);
if(fu != fv){
father[fu] = fv;
ans += e[i].cost;
num_edge++;
}
}
return ans;
}
int main(){
int n, m, u, v, cost;//n个点，m条边
while(cin >> n && n != 0){
m = n * (n-1) / 2;
for(int i = 0; i < m; i++){
cin >> u >> v >> cost;
e[i].u = u;
e[i].v = v;
e[i].cost = cost;
}
cout << kruskal(n, m) << endl;
}
return 0;
}
例题11.5继续畅通工程（浙江大学上机）
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int father[100];
struct edge{
int u, v;//表示边的两个端点
int cost;//表示花费
int build;//表示是否已经修建
}e[5000];
bool cmp1(edge a, edge b){
return a.cost < b.cost;
}
int findroot(int x){
if(x == father[x]) return x;
else{
int f = findroot(father[x]);
father[x] = f;
return f;
}
}
int kruskal(int n, int m){
sort(e, e + m, cmp1);
for(int i = 0; i < n; i++) father[i] = i;
int ans = 0, edge_num = 0;
for(int i = 0; i < m; i++){
int fu = findroot(e[i].u);
int fv = findroot(e[i].v);
if(fu != fv){
father[fu] = fv;//合并
ans += e[i].cost;
}
}
return ans;
}
int main(){
int n, m, u, v, cost, build;
while(cin >> n && n != 0){
m = n * (n - 1) / 2;
for(int i = 0; i < m; i++){
cin >> u >> v >> cost >> build;
father[u] = v;
e[i].u = u;
e[i].v = v;
if(build == 0) e[i].cost = cost;
else e[i].cost = 0;
}
cout << kruskal(n, m) << endl;
}
return 0;
}
习题11.4 Freckles（北京大学复试上机）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct edge{//定义边
int u, v;
double cost;
}e[5000];
struct point{//定义点
double x, y;
}p[100];
bool cmp1(edge a, edge b){//定义比较函数
return a.cost < b.cost;
}
int father[100];
int findroot(int x){//找根结点，并且剪枝
if(x == father[x]) return x;
else{
int f = findroot(father[x]);
father[x] = f;
return f;
}
}
double kruskal(int n, int m){
sort(e, e + m, cmp1);
double ans = 0;
for(int i = 0; i < n; i++) father[i] = i;//初始化并查集
for(int i = 0; i < m; i++){
int fu = findroot(e[i].u);
int fv = findroot(e[i].v);
if(fu != fv){
father[fu] = fv;
ans += e[i].cost;
}
}
return ans;
}
double lengthcost(double a, double b, double c, double d){//计算两个点之间的距离
double temp = (a-c)*(a-c) + (b-d)*(b-d);
return sqrt(temp);
cout << " te = " << endl;
}
int main(){
int n, m;//n个点，m个边
cin >> n;
m = n *(n - 1) / 2;
for(int i = 0; i < n; i++){//输入点
cin >> p[i].x >> p[i].y;
}
int num_m = 0;//开始初始化边的个数
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
father[i] = j;//i点和j点连接
e[num_m].u = i;//定义边的两个点
e[num_m].v = j;
e[num_m].cost = lengthcost(p[i].x, p[i].y, p[j].x, p[j].y);//定义边的=距离
num_m++;
}
}
double t = kruskal(n, m);
printf("%.2f\n", t);
return 0;
}
例题11.7最短路径问题（浙江大学上机）
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXV = 1010;
const int INF = 100000000;
int n, m, s, t;//定义n个点，m个边,源点s,目的点t
int G[MAXV][MAXV], cost[MAXV][MAXV];//无向图采用邻接矩阵
int d[MAXV], c[MAXV];//定义距离和花费
bool vis[MAXV] = {false};//标记数组
void Dijstra(int s){
fill(d, d + MAXV, INF);
fill(c, c + MAXV, INF);
c[s] = 0;
d[s] = 0;
for(int i = 1; i <= n; i++){
int u = -1, MIN = INF;//u为当前点，MIN为当前最小值
for(int j = 1; j <= n; j++){//找到与u相连的距离最小的点
if(vis[j] == false && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if(u == -1) return;//找不到与u相连的点就退出
vis[u] = true;
for(int v = 1; v <= n; v++){
if(vis[v] == false && G[u][v] != INF ){
if(d[u] + G[u][v] < d[v]){
d[v] = d[u] + G[u][v];
c[v] = c[u] + cost[u][v];
}else if(d[u] + G[u][v] == d[v] && c[u] + cost[u][v] < c[v]){
c[v] = c[u] + cost[u][v];
}
}
}
}
}
int main(){
while(cin >> n >> m){
if(n == 0 && m == 0) break;
fill(G[0], G[0] + MAXV * MAXV, INF);//图的初始化
for(int i = 0; i < m; i++){//用于输入
int ta, tb, td, tp;
cin >> ta >> tb >> td >> tp;
if(G[ta][tb] > td){
G[ta][tb] = G[tb][ta] = td;//G存距离，coat存花费
cost[ta][tb] = cost[tb][ta] = tp;
}else if(G[ta][tb] == td && cost[ta][tb] < tp){
cost[ta][tb] = cost[tb][ta] = tp;
}
}
cin >> s >> t;
Dijstra(s);
cout << d[t] << " " << c[t] << endl;
}
return 0;
}