# 基礎圖論
# 10/21 武陵資讀
## Grid Graph
### ocean / land
* DFS
* BFS
[ZJ b701](https://zerojudge.tw/ShowProblem?problemid=b701)
```c
#include<bits/stdc++.h>
using namespace std;
int r,c,sum;
int W=513,N=513,E=-1,S=-1;
void check(int i,int j){
if(i<N) N=i;
if(i>S) S=i;
if(j<W) W=j;
if(j>E) E=j;
}
int pos[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
vector<vector<int> > graph;
void DFS(int i,int j){
sum++;
check(i,j);
graph[i][j]=-1;
for(auto I:pos){
if(graph[i+I[0]][j+I[1]]==1){
DFS(i+I[0],j+I[1]);
}
}
}
int main(){
cin.tie(0);
cin.sync_with_stdio(0);
cin>>r>>c;
graph.resize(r,vector<int>(c));
for(int i=0;i<r;i++)for(int j=0;j<c;j++) cin>>graph[i][j];
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(graph[i][j]==1){
DFS(i,j);
cout<<W<<" "<<N<<" "<<E<<" "<<S<<" "<<sum<<'\n';
W=513,N=513,E=-1,S=-1,sum=0;
}
}
}
return 0;
}
```
### Maze shortest path
* BFS
[ZJ a982](https://zerojudge.tw/ShowProblem?problemid=a982)
```c
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(0);ios_base::sync_with_stdio(0);
int n;
int pos[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
inline bool in(int x,int y){
return (1<=x&&x<n-1&&1<=y&&y<n-1 );
}
int main(){
IOS
bool flag=false;
char ch;
int cur=0,ans;
cin>>n;
int graph[n][n];
pair<int,int> Start={2,2},End={n-1,n-1};
memset(graph,0,n*n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>ch;
graph[i][j]=(ch=='#' ? -1:0);
}
}
queue<pair<int,int> > q;
q.push(Start);
graph[1][1]=1;
while(q.size()){
int x_=q.front().first,y_=q.front().second;
if(q.front()==End){
ans=graph[x_-1][y_-1];
flag=true;
break;
}
for(int i=0;i<4;i++){
int X=x_+pos[i][0],Y=y_+pos[i][1];
if(in(X-1,Y-1)){
if(!graph[X-1][Y-1]){
graph[X-1][Y-1]=graph[x_-1][y_-1]+1;
q.push({X,Y});
}
}
}
q.pop();
}
if(flag) cout<<ans;
else cout<<"No solution!";
return 0;
}
```
* BFS 8 direction
[ZJ b059](https://zerojudge.tw/ShowProblem?problemid=b059)
```c
#include<bits/stdc++.h>
using namespace std;
#define N 100
int n,x,y;
int Graph[101][101];
int pre[4][2]={{-1,0},{0,-1},{1,0},{0,1}},pos[4][2][2]={ { {-3,1},{-3,-1} } , { {-1,-3},{1,-3} } , { {3,-1},{3,1} } , { {-1,3},{1,3} } };
pair<int,int > Start,End,cur;
void slove(){
bool flag=false;
memset(Graph,0,sizeof(Graph));
for(int i=0;i<n;i++){
cin>>x>>y;
Graph[x][y]=-1;
}
cin>>x>>y;
Start={x,y};
cin>>x>>y;
End={x,y};
queue<pair<int,int> > q;
q.push(Start);
Graph[Start.first][Start.second]=1;
while(q.size()){
cur=q.front();
x=cur.first,y=cur.second;
if(x==End.first&&y==End.second){
flag=true;
break;
}
q.pop();
for(int i=0,X,Y;i<4;i++){
X=x+pre[i][0],Y=y+pre[i][1];
if(X<0||X>=N||Y<0||Y>=N||Graph[X][Y]==-1) continue;
for(int j=0;j<2;j++){
X=x+pos[i][j][0],Y=y+pos[i][j][1];
if(X<0||X>=N||Y<0||Y>=N||Graph[X][Y]!=0) continue;
Graph[X][Y]=Graph[x][y]+1;
q.push({X,Y});
}
}
}
if(flag){
cout<<Graph[End.first][End.second]-1<<'\n';
}
else{
cout<<"impossible\n";
}
}
int main(){
cin.tie(0);ios_base::sync_with_stdio(0);
while(cin>>n){
slove();
}
return 0;
}
```
## Graph
### Graph presentation
[ZJ a796](https://zerojudge.tw/ShowProblem?problemid=a796)
```cpp=typedef pair<int,int> pii;
const int MAX_N = 1e6+5;
const int INF = 1e9;
bool G[105][105]={};
int cnt[105]={};
int main(){
OAO
memset(G,0,sizeof(G));
int n,m,q,u,v;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>u>>v;
G[u][v]=G[v][u]=1;
cnt[u]++;
cnt[v]++;
}
cin>>q;
while(q--){
cin>>m;
if(m==1){
cin>>m;
cout<<cnt[m]<<'\n';
}
else{
cin>>u>>v;
cout<<(G[u][v] ? "Yes\n":"No\n");
}
}
return 0;
}
```
[ZJ f668](https://zerojudge.tw/ShowProblem?problemid=f668)
* Adjacency Matrix
* Adjacency List
```c
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(0);ios_base::sync_with_stdio(0);
int n,m,a,b;
void slove(){
vector<vector<int> > graph(n+1,vector<int >(n+1,0));
while(m--){
cin>>a>>b;
graph[a][b]=b,graph[b][a]=a;
}
for(int i=1;i<=n;i++){
cout<<i<<": ";
for(int j=1;j<=n;j++){
if(graph[i][j]) cout<<graph[i][j]<<' ';
}
cout<<'\n';
}
}
int main(){
IOS
while(cin>>n>>m){
slove();
}
return 0;
}
```
### Connection
[ZJ a290](https://zerojudge.tw/ShowProblem?problemid=a290)
* Check A and B are connected
* DFS
* BFS
```c
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
bool Find;
vector<vector<int> > graph;
vector<bool > visited;
void DFS(int node){
if(node==b){
Find=true;
return;
}
for(auto i:graph[node]){
if(!visited[i]){
visited[i]=true;
DFS(i);
}
}
}
void slove(int n,int m){
Find=false;
graph.resize(n+1);
visited.resize(n+1,0);
for(int i=1;i<=m;i++){
cin>>a>>b;
graph[a].emplace_back(b);
}
cin>>a>>b;
DFS(a);
cout<<(Find ? "Yes!!!":"No!!!")<<'\n';
graph.clear();
visited.clear();
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
while(cin>>n>>m){
slove(n,m);
}
}
```
### DFS max path
[ZJ d908](https://zerojudge.tw/ShowProblem?problemid=d908)
* directed
* vertex weight
:::spoiler **Hint**
* 跑過所有有可能的路徑
* 取最大
:::
```c
#include<bits/stdc++.h>
using namespace std;
#define N 105
typedef pair<int, int > pii;
string start,u,v;
map<string ,int> M;
vector<pii> Graph[N];
int n,cnt=0,w,MAX=0;
inline void DFS(int U,int cur){
MAX=max(MAX,cur);
for(auto V : Graph[U]){
DFS(V.first,cur+V.second);
}
}
int main(){
cin.tie(0);ios_base::sync_with_stdio(0);
cin>>start>>n;
M[start]=cnt++;
for(int i=0;i<n;i++){
cin>>u>>v>>w;
if(M.find(u)==M.end()) M[u]=cnt++;
if(M.find(v)==M.end()) M[v]=cnt++;
Graph[M[u]].push_back({M[v],w});
}
DFS(M[start],0);
cout<<MAX;
return 0;
}
```
### DFS min value
[ZJ c812](https://zerojudge.tw/ShowProblem?problemid=c812)
* directed
* weighted
* min value in DFS path
```c
#include<bits/stdc++.h>
using namespace std;
#define N 5005
int q,V,n,ans=0;
vector<pair<int,int > > Graph[N];
bool visited[N];
// first : node , second : val
void DFS(int U,int val){
if(val>=q) ans++;
for(auto u:Graph[U]){
if(visited[u.first]) continue;
visited[u.first]=1;
DFS(u.first,min(val,u.second));
}
}
int main(){
cin.tie(0);ios_base::sync_with_stdio(0);
cin>>n>>V>>q;
memset(visited,0,sizeof(visited));
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
Graph[u].push_back({v,w});
Graph[v].push_back({u,w});
}
visited[V]=1;
for(auto v:Graph[V]){
visited[v.first]=1;
DFS(v.first,v.second);
}
cout<<ans;
return 0;
}
```
### Bipartite
[Tcirc d100](https://judge.tcirc.tw/ShowProblem?problemid=d100)
* BFS
```c
#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e4+5;
// AC bipartite graph
int main(){
cin.tie(0);ios_base::sync_with_stdio(0);
int T ; cin>>T;
while(T--){
bool flag =true;
int u, v, n , m;
cin>>n>>m;
vector<vector<int> > G(n);
while(m--){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> mark(n,-1);
for(int i=0;i<n && flag ;i++){
if(mark[i]==-1 ){
queue<int> q;
q.push(i);
mark[i]=0;
while(q.size() && flag){
u=q.front();
q.pop();
for(auto v:G[u]){
if(mark[v]==mark[u]){
flag =false;
break;
}
else if(mark[v]==-1){
q.push(v);
mark[v]=!mark[u];
}
}
}
}
}
cout<<(flag ? "yes\n" : "no\n");
}
return 0;
}
```
### DAG topological sort
[ZJ f167](https://zerojudge.tw/ShowProblem?problemid=f167)
* 拓樸排序
```cpp=
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define ll long long
#define range(x) x.begin(),x.end()
#define MEM(x,i) memset(x,i,sizeof(x))
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,st,n) for(int i=st;i<=n;++i)
#define PB emplace_back
typedef pair<int,int> pii;
const int MAX_N = 1e3+5;
const int INF = 1e9;
vector<int> G[MAX_N];
int indeg[MAX_N]={};
int main(){
OAO
int n, m,u,v;
cin>>n>>m;
while(m--){
cin>>u>>v;
G[u].PB(v);
indeg[v]++;
}
queue<int> q;
for(int i=1;i<=n;i++){
if(!indeg[i]) q.push(i);
}
vector<int> order;
while(q.size()){
u=q.front();
order.PB(u);
q.pop();
for(int v:G[u]){
if(--indeg[v]==0 ) {
q.push(v);
}
}
}
if(n==order.size()) {
cout<<"YES\n";
for(int i:order) cout<<i<<'\n';
}
else{
cout<<"NO";
}
return 0;
}
```
[ZJ e999](https://zerojudge.tw/ShowProblem?problemid=e999)
```cpp
#include<bits/stdc++.h>
using namespace std;
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define ll long long
#define range(x) x.begin(),x.end()
#define MEM(x,i) memset(x,i,sizeof(x))
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,st,n) for(int i=st;i<=n;++i)
#define PB emplace_back
typedef pair<int,int> pii;
const int MAX_N = 1e6+5;
const int INF = 1e9;
vector<int> G[MAX_N];
int indeg[MAX_N]={},outdeg[MAX_N]={},Dis[MAX_N]={},n,m;
int main(){
OAO
cin>>n>>m;
int u,v;
while(m--){
cin>>u>>v;
G[u].PB(v);
indeg[v]++;
outdeg[u]++;
}
queue<int> q;
for(int i=0;i<n;i++){
if(!indeg[i]) q.push(i);
}
while( q.size() ){
u=q.front();
q.pop();
for(const int &v:G[u]){
Dis[v]+=(Dis[u]==0 ? 1:Dis[u]);
if(--indeg[v]==0){
q.push(v);
}
}
}
int ans=0;
for(int i=0;i<n;i++){
if(!outdeg[i]) ans+=Dis[i];
}
cout<<ans;
return 0;
}
```
Sign in with Wallet
Connect another wallet