基礎圖論

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