洛谷题单 -- 图论的简单入门_b3643 图的存储

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;
}