Solution of Light OJ 1257 - Farthest Nodes in a Tree (II)

We may solve using BFS of DFS. Both solutions are given.
Using BFS:

/* Bismillahir Rahmanir Rahim Solution-Using BFS Find the farthest two nodes and calculate all nodes distance from both farthest nodes and take the maximum for each node */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fii(i, n, m) for(int i=n; i<=m; i++) using namespace std; vector<int>vt[30001], cost[30001]; int n, dis[30001], dis1[30001], a1, a2, p, cnt=0; void bfs(int st){ fi(0, n) dis[i]=-1; int mx=-1; queue<int>q; q.push(st); dis[st]=0; while(!q.empty()){ int u=q.front(); q.pop(); if(mx<dis[u]){ mx=dis[u]; p=u; } for(int j=0; j<vt[u].size(); j++){ int v=vt[u][j]; if(dis[v]==-1){ dis[v]=dis[u]+cost[u][j]; q.push(v); } } } } void bfs1(int st){ fi(0, n) dis1[i]=-1; queue<int>q; q.push(st); dis1[st]=0; while(!q.empty()){ int u=q.front(); q.pop(); for(int j=0; j<vt[u].size(); j++){ int v=vt[u][j]; if(dis1[v]==-1){ dis1[v]=dis1[u]+cost[u][j]; q.push(v); } } } } int main() { int t, cs=1, u, v, w; scanf("%d", &t); while(t--){ scanf("%d", &n); fi(1, n-1){ scanf("%d%d%d", &u, &v, &w); vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } bfs(0); // find an ending point of farthest path a1=p; // find another ending point a2 and distance from a1 (dis[]) bfs(a1); a2=p; bfs1(a2); //calculating distance from a2(dis1[]) printf("Case %d:\n", cs++); fi(0, n-1){ printf("%d\n", max(dis[i], dis1[i])); vt[i].clear(); cost[i].clear(); } } return 0; }

Using DFS:

/* Bismillahir Rahmanir Rahim Solution-Using DFS Find the farthest two nodes and calculate all nodes distance from both farthest nodes and take the maximum for each node */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fii(i, n, m) for(int i=n; i<=m; i++) using namespace std; vector<int>vt[30009], cost[30009]; int dis[30009], dis1[30009], vis[30009], n, p, mx; void dfs(int at){ if(vis[at]) return ; else{ vis[at]=1; if(mx<dis[at]){ mx=dis[at]; p=at; } for(int j=0; j<vt[at].size(); j++){ int v=vt[at][j]; if(dis[v]==-1){ dis[v]=dis[at]+cost[at][j]; dfs(v); } } } } void dfs1(int at){ if(vis[at]) return ; else{ vis[at]=1; for(int j=0; j<vt[at].size(); j++){ int v=vt[at][j]; if(dis1[v]==-1){ dis1[v]=dis1[at]+cost[at][j]; dfs1(v); } } } } int main(){ int t, cs=1, u, v, w, a1, a2; scanf("%d", &t); while(t--){ scanf("%d", &n); fi(1, n-1){ scanf("%d%d%d", &u, &v, &w); vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } fi(0, n+1){vis[i]=0; dis[i]=-1;} mx=0, dis[0]=0; dfs(0); // find an ending point of farthest path a1=p, mx=0; fi(0, n+1){vis[i]=0; dis[i]=-1;} dis[a1]=0; // find another ending point a2 and distance from a1(dis[]) dfs(a1); a2=p; fi(0, n+1){vis[i]=0; dis1[i]=-1;} dis1[a2]=0; dfs1(a2);//calculating distance from a2(dis1[]) printf("Case %d:\n", cs++); fi(0, n-1){ printf("%d\n", max(dis[i], dis1[i])); vt[i].clear(); cost[i].clear(); } } return 0; }

Solution of Light OJ 1049 - One Way Roads

/* Bismillahir Rahmanir Rahim Solution-Using DFS Apply DFS from the first node in two way & get the minimum */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) using namespace std; vector<int>vt[101], cost[101]; int sts[101][101], vis[101], ans, st, en; void dfs(int at){ if(vis[at]) return ; else{ vis[at]=1; if(at==1){ // its for the first node, use only one way(st) int v=vt[at][st]; // here st=0 or 1 if(!vis[v]){ if(sts[at][v]) // if(redirecting road) ans=ans+cost[at][st]; en=v; // saving the last node of the DFS dfs(v); } } else{ for(int j=0; j<vt[at].size(); j++){ int v=vt[at][j]; if(!vis[v]){ if(sts[at][v]) ans=ans+cost[at][j]; // same en=v; // same as before dfs(v); } } } } } int main(){ int t, cs=1, a, b, c, n, a1, a2; cin>>t; while(t--){ cin>>n; fi(1, n){ cin>>a>>b>>c; vt[a].push_back(b); sts[a][b]=0; // normal road vt[b].push_back(a); sts[b][a]=1; // redirecting road cost[a].push_back(c); cost[b].push_back(c); } fi(0, n) vis[i]=0; ans=0, st=1; dfs(1); a1=ans; if(sts[en][1]) a1=a1+cost[1][0]; //if(redirecting road) fi(0, n) vis[i]=0; ans=0, st=0; dfs(1); a2=ans; if(sts[en][1]) a2=a2+cost[1][1]; //same as before ans=min(a2, a1); cout<<"Case "<<cs++<<": "<<ans<<endl; fi(0, n) {vt[i].clear(); cost[i].clear();} } return 0; }

Solution of Light OJ 1337 - The Crystal Maze

/* Bismillahir Rahmanir Rahim Solution-Using DFS Firstly visit all nodes and keeping answer in every node **Input section is long not the main code** */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fii(i, n, m) for(int i=n; i<=m; i++) using namespace std; vector<int>vc, vt[250009]; int vis[250009], sts[250009], n, m, q, cnt, x, y, ans; void dfs(int at){ if(vis[at]) return ; else{ vis[at]=1; if(sts[at]==1) cnt++; // if(node=='C') vc.push_back(at); //storing-the nodes in a chain for(int z=0; z<vt[at].size(); z++){ int v=vt[at][z]; if(!vis[v] && sts[v]!=-1){ dfs(v); } } } } int main(){ int t, cs=1, ans[250009]; cin>>t; while(t--){ cnt=0; cin>>n>>m>>q; fii(i, 1, n){ char ch; cin>>ch; cnt++; if(ch=='#') sts[cnt]=-1; else if(ch=='.') sts[cnt]=0; else sts[cnt]=1; if(i!=1){ vt[cnt].push_back(cnt-m); vt[cnt-m].push_back(cnt); } fii(j, 2, m){ cin>>ch; cnt++; if(ch=='#') sts[cnt]=-1; else if(ch=='.') sts[cnt]=0; else sts[cnt]=1; vt[cnt].push_back(cnt-1); vt[cnt-1].push_back(cnt); if(i!=1){ vt[cnt].push_back(cnt-m); vt[cnt-m].push_back(cnt); } } } fi(0, n*m) vis[i]=0; fi(1, n*m){ cnt=0; if(sts[i]!=-1) dfs(i); // if(node!='#') //cnt=total Crystal; ans[every node in this chain]=cnt; for(int zz=0; zz<vc.size(); zz++) ans[vc[zz]]=cnt; vc.clear(); } cout<<"Case "<<cs++<<":"<<endl; fi(1, q){ cin>>x>>y; x=(x-1)*m+y; // one dimensional position not (x, y) cout<<ans[x]<<endl; } fi(0, n*m) vt[i].clear(); } return 0; }

Solution of Light OJ 1009 - Back to Underworld

/* Bismillahir Rahmanir Rahim Solution-Using DFS We will color all the nodes. If first node is white(1) then all the children of first node is black(-1). */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fii(i, n, m) for(int i=n; i<=m; i++) using namespace std; vector<int>vt[20009]; int vis[20009], s, cnt, pr[20009], sts[20009]; void dfs(int at){ if(vis[at]) return ; else{ vis[at]=1; sts[at]=sts[pr[at]]*(-1); //if parent=-1 then child=1; cnt++; s=s+sts[at]; fii(i, 0, vt[at].size()-1){ int v=vt[at][i]; if(!vis[v]) pr[v]=at; dfs(v); } } } int main(){ int t, n, cs=1, mx, a, b, ans; cin>>t; while(t--){ set<int>st; set<int>::iterator it; mx=0, ans=0; cin>>n; fi(1, n){ cin>>a>>b; vt[a].push_back(b); vt[b].push_back(a); st.insert(a); st.insert(b); mx=max(mx, max(a, b)); } fi(0, mx){ vis[i]=0, pr[i]=i, sts[i]=0; } for(it=st.begin(); it!=st.end(); it++){ cnt=0, s=0; if(vis[*it]==0){ sts[*it]=1; dfs(*it); if(s<0) s=s*(-1); //technique to find maximum Vampires/Lykans s=(cnt+s)/2; ans=ans+s; } } cout<<"Case "<<cs++<<": "<<ans<<endl; for(it=st.begin(); it!=st.end(); it++){ vt[*it].clear(); } } return 0; }