### washen_Data's blog

By washen_Data, history, 9 months ago, ,

# Storage

Adjacency matrix: Double loop markup implementation. Code： ~~~~~

# include

using namespace std;

# define maxn 5039

int a[maxn][maxn]; int n,m; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); a[x][y] = z; //a[y][x] = z; } } ~~~~~

Use vector storage to reduce space. Code: ~~~~~

# include

using namespace std; struct Edge{int x,y,z;}; vector f[5039]; void add(int x,int y,int z){f[x].push_back((Edge){y,z});} int n,m; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); //add(y,x,z); }
} ~~~~~

# DFS

Search and judge on the basis of storage. Code: ~~~~~

# include

using namespace std;

# define maxn 5039

int a[maxn][maxn]; int g[maxn]; int n,m; void dfs(int v){ if(g[v])return; g[v] = 1; printf("%d ",v); for(int i=1;i<=n;i++) if(a[v][i])dfs(i); return; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); a[x][y] = 1; //a[y][x] = 1; } dfs(1); return 0; } ~~~~~

# BFS

Search and judge on the basis of storage. Code: ~~~~~

# include

using namespace std;

# define maxn 5039

int a[maxn][maxn]; int g[maxn]; int n,m; queue q; void bfs(int num){ q.push(num); int head; g[num] = 1; while(!q.empty()){ head = q.front(); printf("%d ",head); q.pop(); for(int i=1;i<=n;i++){ if(a[head][i] && !g[i]){ g[i] = 1; q.push(i); } } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); a[x][y] = 1; //a[y][x] = 1; } bfs(1); return 0; } ~~~~~

# Topological Sorting

Judgment Degree+DFS Code: ~~~~~

# include

using namespace std; vectorf[200001]; int in[200001],a[200001]; void add(int x,int y){f[x].push_back(y);} queueq; int n,m; void topo_sort(){ while(!q.empty())q.pop(); for(int i=1;i<=n;i++) if(!in[i])q.push(i); while(!q.empty()){ int cur = q.front(); q.pop(); for(int i=0;i<f[cur].size();i++){ in[f[cur][i]]--; if(!in[f[cur][i]])q.push(f[cur][i]); // ... } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); add(y,x); in[x]++; } topo_sort(); //... return 0; } ~~~~~

• -28

 » 9 months ago, # |   0 Auto comment: topic has been updated by washen_Data (previous revision, new revision, compare).
 » 9 months ago, # |   +8 WOW