Try   HackMD

基礎圖論

10/21 武陵資讀

Grid Graph

ocean / land

#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

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

#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

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

  • Adjacency Matrix
  • Adjacency List
#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

  • Check A and B are connected
  • DFS
  • BFS
#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

  • directed
  • vertex weight
Hint
  • 跑過所有有可能的路徑
  • 取最大
#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

  • directed
  • weighted
  • min value in DFS path
#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

  • BFS
#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

  • 拓樸排序

























































#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


#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;
}
Last changed by 
 
JasonLiu
https://github.com/jason810496/ https://www.linkedin.com/in/zhe-you-liu/ https://blog.zhu424.dev
0
207

Read more

NCKU CSIE PD1 Week15

👉English

Dec 12, 2023
NCKU CSIE PD1 Week15 English

If you already know what Generic Programming is,you can jump directly to Lab.

Dec 12, 2023
2023 SITCON 台南 HoC

都只有教到 for loop，差別在國小是用 Blocky (scratch) ， 國中以上是用 Python 來完成

Dec 10, 2023
基礎 Python 上課筆記

[]

Jul 13, 2023
Read more from JasonLiu
Published on HackMD