#include <iostream> #include <string.h> #include <vector> #include <map> #define ll long long #define INF 1000000000 using namespace std; int graph[25][25]; int N,M,MiN; int sum[25]; map<int,string> m; int main() { int t,kase=1; int a,b,c,res; string s; //cin>>t; while(cin>>N) { cin>>M; if(N==0 ) break; //mp.clear(); m.clear(); int x=1; for(int i=1;i<25;i++) { sum[i]=0; for(int j=1;j<25;j++) { graph[i][j]=INF; if(i==j)
Category: Graph Algorithm
208
#include <iostream> #include <string.h> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int mat[25][25]; int dist[25][25]; vector<int> vb[25]; bool visit[25]; int fire; int kase=1; int mx=0,cnt=0; int res[25]; void dfs(int s,int k) { if(s==fire) { cnt++; for(int i=0;i<k;i++) { cout<<res[i]<<(i==(k-1)?"\n":" "); } return; } //for(int i=0;i<vb[s].size();i++) for(int i=1;i<=mx;i++) { if(visit[i]) continue; if(!mat[s][i]) continue; if(!dist[i][fire])
459
This problem can be solved using dfs,bfs or union find algorithm, BFS solution: #include <iostream> #include <stdio.h> #include <string.h> #include <map> #include <queue> #include <string> using namespace std; int to; bool visit[26]; int graph[26][26]; void bfs(int a) { int b; queue<int> q; q.push(a); while(!q.empty()) { b =q.front(); q.pop(); visit[b]=1; for(int i=0;i<=to;i++) { if(graph[b][i]==1 && visit[i]==0)
10308
This is the problem to find the tree diameter. #include <iostream> #include <fstream> #include <sstream> #include <map> #include <vector> #include <string> #include <queue> #include <string.h> #include <stdio.h> #define ull unsigned long long #define SZ 10002 #define FOR(i,a) for(int i=0;i<a;i++) using namespace std; vector<int> graph[SZ]; bool visit[SZ]; int distnce[SZ][SZ]; ull distnode[SZ]; ull max_dist=0; int farthestnode; void
11709
#include <iostream> #include <map> #include <vector> #include <string> #include <queue> #include <string.h> #include <stdio.h> using namespace std; vector<int> graph[1005]; bool visit[1005]; bool visited[1005][1005]; map<string,int> mp; int p,t; void dfs(int u,int v) { visited[u][v]=1; int tmp; for(int i=0;i<graph[v].size();i++) { tmp=graph[v][i]; if(!visited[u][tmp]) { dfs(u,tmp); } } } int main() { string s,s1; while(cin>>p>>t) { if(p==0 && t==0)
341
#include <iostream> #include <stdio.h> #include <vector> #define inf 1000000000 using namespace std; vector<int> v; int path[11][11]; int NExt[11][11]; bool first; /* void find_path(int a,int b) { v.push_back(b); while(NExt[a][b]!=-1) { v.push_back(NExt[a][b]); b=NExt[a][b]; } v.push_back(a); } */ void find_path(int i,int j) { if(NExt[i][j]==-1) if(first) { cout<<i<<" "<<j; first=false; } else { cout<<" "<<j; } else { find_path(i,NExt[i][j]);