B3643 圖的存儲
鏈接 :?
圖的存儲 - 洛谷
思路 :?
這一題要考察圖的存儲方式 , 一般可以使用鄰接矩陣 或 鄰接表來存儲 圖的結(jié)點(diǎn) 和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】查找文獻(xiàn)
鏈接?
【深基18.例3】查找文獻(xiàn) - 洛谷
思路 :?
這題考察有向圖的 dfs 和 bfs ,詳情請看代碼,如果用鄰接矩陣的話一定會mle,只能夠使用鄰接表，我這里采用的是用vector數(shù)組實現(xiàn)的鄰接表,詳情請看代碼 :?
代碼?
#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] ; // 狀態(tài)記錄數(shù)組
vector<int> a[N] ; // 鄰接表
queue<int> q;
inline int read(){//二進(jìn)制優(yōu)化的快讀
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指當(dāng)前遍歷到的結(jié)點(diǎn),r表示已遍歷過的結(jié)點(diǎn)
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數(shù)組
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()); // 將每條路通向的點(diǎn)從小到大排序
dfs(1,0) ; // 深搜
puts("");
for(int i=1;i<=n;i++) b[i] = false ;
bfs(1) ; // 寬搜
puts("") ;
return 0;
}B3644 【模板】拓?fù)渑判?/ 家譜樹
鏈接 :
?https://www.luogu.com.cn/problem/B3644
思路 :?
給出案例畫圖如下 :?
拓?fù)渑判?模板題)
代碼 :?
#include<bits/stdc++.h>
using namespace std;
const int N = 102 ;
vector<int> a[N] ;
int tp[N] ; // 存放拓?fù)湫蛄?
int d[N] ; // 存放每個結(jié)點(diǎ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 的點(diǎn)全放進(jìn)來
}
}
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] ; // 存放每個結(jié)點(diǎ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 的點(diǎn)全放進(jìn)來
}
}
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 圖的遍歷
鏈接 :?
圖的遍歷 - 洛谷文章來源：http://www.zghlxwxcb.cn/news/detail-850290.html
思路 :?
反向建邊 + dfs :?文章來源地址http://www.zghlxwxcb.cn/news/detail-850290.html
代碼 :?
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10 ;
vector<int> g[N] ;
int n , m ;
int ans[N] ;
// 反向建圖 + dfs
// 考慮較大的點(diǎn)能夠法相到達(dá)那一些點(diǎn)
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進(jìn)行dfs
for(int i=1;i<=n;i++){
cout << ans[i] << " " ;
// if(ans[i]) cout << ans[i] << endl ;
// else cout << i << endl ;
}
return 0;
}到了這里，關(guān)于洛谷題單 -- 圖論的簡單入門的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
