washen_Data's blog

By washen_Data, history, 5 weeks ago, In English,

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

Adjacency table:

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

include

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

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

include

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

 
 
 
 
  • Vote: I like it
  • -28
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by washen_Data (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

WOW