B3643 图的存储
链接 :
图的存储 - 洛谷
思路 :
这一题要考察图的存储方式 , 一般可以使用邻接矩阵 或 邻接表来存储 图的结点 和1 边的信息 ，详情请看代码 :
代码
#include<bits/stdc++.h>
using namespace std;const int N = 1010 ;
int n , m ;
int a[N][N] ; // 邻接矩阵
vector<int> b[N]; // 邻接表 // 邻接矩阵的输出
void pa(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout << a[i][j] << " ";}cout << endl ;}
}// 邻接表的输出
void pb(){for(int i=1;i<=n;i++){int d = b[i].size();cout << d << " ";sort(b[i].begin(),b[i].end());for(int j=0;j<d;j++){cout << b[i][j] << " ";}cout << endl ;}
}int main(){cin >> n >> m;for(int i=0;i<m;i++){int x , y ; cin >> x >> y ;a[x][y] = 1 ; a[y][x] = 1 ; // 邻接矩阵b[x].push_back(y) ; b[y].push_back(x) ; // 邻接表 }pa();pb();return 0 ;
}P5318 【深基18.例3】查找文献
链接
【深基18.例3】查找文献 - 洛谷
思路 :
这题考察有向图的 dfs 和 bfs ,详情请看代码,如果用邻接矩阵的话一定会mle,只能够使用邻接表，我这里采用的是用vector数组实现的邻接表,详情请看代码 :
代码
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10 ;
typedef long long LL ;int n , m , x , y;
bool b[N] ; // 状态记录数组
vector<int> a[N] ; // 邻接表
queue<int> q;inline int read(){//二进制优化的快读 int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
}// x指当前遍历到的结点,r表示已遍历过的结点
void dfs(int x , int r){ b[x] = true ;cout << x << " " ; // 输出if(r == n) return ;for(int i=0;i<a[x].size();i++){if(!b[a[x][i]])dfs(a[x][i],r+1);}
}void bfs(int x){memset(b , false , sizeof(b)) ; // 清空bool数组b[x] = true ;q.push(x) ;while(!q.empty()){ // 还有没有没访问的 int v = q.front();q.pop() ; // 弹出队头 , 否则会一直在第一层遍历cout << v << " " ;for(int i=0;i<a[v].size();i++){if(!b[a[v][i]]){b[a[v][i]] = true ;q.push(a[v][i]);}} }
}int main(){// n = read() ; m = read() ;cin >> n >> m ;for(int i=1;i<=m;i++){x = read() ; y = read() ; // cin >> x >> y ; a[x].push_back(y);}for(int i=1;i<=n;i++) sort(a[i].begin(),a[i].end()); // 将每条路通向的点从小到大排序 dfs(1,0) ; // 深搜 puts("");for(int i=1;i<=n;i++) b[i] = false ;bfs(1) ; // 宽搜 puts("") ;return 0;
}B3644 【模板】拓扑排序 / 家谱树
链接 :
https://www.luogu.com.cn/problem/B3644
思路 :
给出案例画图如下 :
拓扑排序(模板题)
代码 :
#include<bits/stdc++.h>
using namespace std;const int N = 102 ;vector<int> a[N] ;
int tp[N] ; // 存放拓扑序列
int d[N] ; // 存放每个结点的入度
int n , x ;bool toposort() {queue<int> q;int tt = 0 ;for(int i = 1; i <= n; i++) {if(d[i] == 0) {q.push(i); // 将入度为 0 的点全放进来 }}while(!q.empty()) {int u = q.front() ; q.pop();tp[++tt] = u ;for(auto v : a[u]) {d[v] -- ;if(d[v] == 0){q.push(v);}}}return tt == n;
}int main(){scanf("%d",&n);for(int i=1;i<=n;i++){while(cin >> x){if(x == 0) break;a[i].push_back(x);d[x] ++;}} if(toposort()) {for(int i=1;i<=n;i++){cout << tp[i] << " ";}cout << endl ;}else{return 0;}return 0 ;
}或者说这样 :
#include<bits/stdc++.h>
using namespace std;const int N = 102 ;vector<int> a[N] ;
int d[N] ; // 存放每个结点的入度
int n , x ;bool toposort() {queue<int> q;vector<int> res;for(int i = 1; i <= n; i++) {if(d[i] == 0) {q.push(i); // 将入度为 0 的点全放进来 }}while(!q.empty()) {int u = q.front() ; q.pop();res.push_back(u);for(auto v : a[u]) {d[v] -- ;if(d[v] == 0){q.push(v);}}}if(res.size()==n) {for(auto x : res) cout << x << " ";return true;}else {return false;}
}int main(){scanf("%d",&n);for(int i=1;i<=n;i++){while(cin >> x){if(x == 0) break;a[i].push_back(x);d[x] ++;}} if(toposort()) {return 0 ;}return 0 ;
}P3916 图的遍历
链接 :
图的遍历 - 洛谷
思路 :
反向建边 + dfs :
代码 :
#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 10 ;
vector<int> g[N] ;
int n , m ;
int ans[N] ;
// 反向建图 + dfs
// 考虑较大的点能够法相到达那一些点 void dfs(int i , int b){if(ans[i]) return ;ans[i] = b ;for(int j=0;j<g[i].size();j++){dfs(g[i][j] , b) ;}
}int main(){cin >> n >> m ;for(int i=0;i<m;i++){int x , y ; cin >> x >> y ;g[y].push_back(x) ; // 反向建边 }for(int i=n;i;i--) dfs(i,i) ; // 对i进行dfs for(int i=1;i<=n;i++){cout << ans[i] << " " ;
// if(ans[i]) cout << ans[i] << endl ;
// else cout << i << endl ;} return 0;
}
