Graph Algorithm – Page 6 – Live with passion

11015

Asif NaeemJanuary 6, 2015

#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)
				graph[i][j]=0;
			}

		}
		for(int i=0;i<N;i++)
		{
			cin>>s;
			m[i+1]=s;
		}

		for(int i=0;i<M;i++)
		{
			cin>>a>>b>>c;
			graph[a][b]=c;
			graph[b][a]=c;
		}

		MiN = INF;
		for(int k=1;k<=N;k++)
		{
			for(int i=1;i<=N;i++)
			{
				for(int j=1;j<=N;j++)
				{
					if(graph[i][j]>(graph[i][k]+graph[k][j]))
						graph[i][j] = (graph[i][k]+graph[k][j]);
				}
			}
		}

		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=N;j++)
			sum[i]+=graph[i][j];

			if(sum[i]<MiN)
			{
				MiN = sum[i];
				res = i;
			}
		}
		cout<<"Case #"<<kase++<<" : "<<m[res]<<"\n";
	}

	return 0;
}

#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)

graph[i][j]=0;

}

for(int i=0;i<N;i++)

{

cin>>s;

m[i+1]=s;

}

for(int i=0;i<M;i++)

{

cin>>a>>b>>c;

graph[a][b]=c;

graph[b][a]=c;

}

MiN = INF;

for(int k=1;k<=N;k++)

{

for(int i=1;i<=N;i++)

{

for(int j=1;j<=N;j++)

{

if(graph[i][j]>(graph[i][k]+graph[k][j]))

graph[i][j] = (graph[i][k]+graph[k][j]);

}

for(int i=1;i<=N;i++)

{

for(int j=1;j<=N;j++)

sum[i]+=graph[i][j];

if(sum[i]<MiN)

{

MiN = sum[i];

res = i;

}

cout<<"Case #"<<kase++<<" : "<<m[res]<<"\n";

}

return 0;

}

208

Asif NaeemDecember 11, 2014

#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])
		continue;

		visit[i]=1;
		res[k] = i;
		dfs(i,k+1);
		visit[i]=0;
		//int d = vb[s][i];
		//if(dist[s][d]==0)//
		//continue;
		//if(visit[d]==0)
		//{
			//visit[d]=1;
			//res[k]=d;
			//dfs(d,k+1);
			//visit[d]=0;
		//}
	}
}


void floyd()
{
	for(int i=1;i<=mx;i++)
	{
		for(int j=1;j<=mx;j++)
		{
			for(int k=1;k<=mx;k++)
			{
				if(dist[j][i]==1 && dist[i][k]==1)
					dist[j][k] = 1;
			}
		}
	}
}


int main()
{
	int a,b,k;

	for(int i=0;i<25;i++)
	{
		res[i] = 0;
	}
	while(scanf("%d",&fire)!=EOF)//cin>>fire
	{
		mx=0;
		memset(mat,0,sizeof(mat));
		memset(dist,0,sizeof(dist));
		while(cin>>a)
		{
			cin>>b;
			if(a==0 && b==0)
			{
				break;
			}

			dist[a][b]=1;
			dist[b][a]=1;

			mat[a][b]=1;
			mat[b][a]=1;
			//vb[a].push_back(b);
			//vb[b].push_back(a);
			mx = max(mx,max(a,b));
		}

		cnt=0;

		/*if(fire==1)
		{
			cout<<"There are "<<0<<" routes from the firestation to streetcorner "<<fire<<".\n";
		}*/
		//else
		memset(visit,0,sizeof(visit));
		visit[1]=1;
		k=0;
		res[k]=1;
		k+=1;
		floyd();
		//for(int i=1; i<=mx; i++)
		//sort(vb[i].begin(), vb[i].end());
		cout<<"CASE "<<kase++<<":\n";
		dfs(1,k);
		cout<<"There are "<<cnt<<" routes from the firestation to streetcorner "<<fire<<".\n";
	}


	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

#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])

continue;

visit[i]=1;

res[k] = i;

dfs(i,k+1);

visit[i]=0;

//int d = vb[s][i];

//if(dist[s][d]==0)//

//continue;

//if(visit[d]==0)

//{

//visit[d]=1;

//res[k]=d;

//dfs(d,k+1);

//visit[d]=0;

//}

}

void floyd()

{

for(int i=1;i<=mx;i++)

{

for(int j=1;j<=mx;j++)

{

for(int k=1;k<=mx;k++)

{

if(dist[j][i]==1 && dist[i][k]==1)

dist[j][k] = 1;

}

int main()

{

int a,b,k;

for(int i=0;i<25;i++)

{

res[i] = 0;

}

while(scanf("%d",&fire)!=EOF)//cin>>fire

{

mx=0;

memset(mat,0,sizeof(mat));

memset(dist,0,sizeof(dist));

while(cin>>a)

{

cin>>b;

if(a==0 && b==0)

{

break;

}

dist[a][b]=1;

dist[b][a]=1;

mat[a][b]=1;

mat[b][a]=1;

//vb[a].push_back(b);

//vb[b].push_back(a);

mx = max(mx,max(a,b));

}

cnt=0;

/*if(fire==1)

{

cout<<"There are "<<0<<" routes from the firestation to streetcorner "<<fire<<".\n";

}*/

//else

memset(visit,0,sizeof(visit));

visit[1]=1;

k=0;

res[k]=1;

k+=1;

floyd();

//for(int i=1; i<=mx; i++)

//sort(vb[i].begin(), vb[i].end());

cout<<"CASE "<<kase++<<":\n";

dfs(1,k);

cout<<"There are "<<cnt<<" routes from the firestation to streetcorner "<<fire<<".\n";

}

return 0;

}

459

Asif NaeemDecember 3, 2014

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)
			{
				q.push(i);
				visit[i]=1;
				graph[b][i]=0;
				graph[i][b]=0;
			}

		}
	}
}

int main()
{
	int t,c=0;
	string s;
	cin>>t;
	scanf("\n");

	while(t--)
	{
		getline(cin,s);
		to = s[0]-65;
		memset(graph,0,sizeof(graph));
		memset(visit,0,sizeof(visit));
		while(1)
		{
			getline(cin,s);
			if(s=="")
			break;
			graph[s[0]-65][s[1]-65]=1;
			graph[s[1]-65][s[0]-65]=1;
		}
		int cnt=0;
		for(int i=0;i<=to;i++)
		{
			if(visit[i]==0)
			{
				bfs(i);
				cnt++;
			}

		}


		cout<<cnt<<endl;
		if(t)
		cout<<endl;

		if(c==t)
		break;
	}
}

#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)

{

q.push(i);

visit[i]=1;

graph[b][i]=0;

graph[i][b]=0;

}

int main()

{

int t,c=0;

string s;

cin>>t;

scanf("\n");

while(t--)

{

getline(cin,s);

to = s[0]-65;

memset(graph,0,sizeof(graph));

memset(visit,0,sizeof(visit));

while(1)

{

getline(cin,s);

if(s=="")

break;

graph[s[0]-65][s[1]-65]=1;

graph[s[1]-65][s[0]-65]=1;

}

int cnt=0;

for(int i=0;i<=to;i++)

{

if(visit[i]==0)

{

bfs(i);

cnt++;

}

cout<<cnt<<endl;

if(t)

cout<<endl;

if(c==t)

break;

}

10308

Asif NaeemNovember 16, 2014

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 bfs(int u)
{
	int tmp;
	memset(visit,0,sizeof(visit));
	int next_node;
	max_dist=0;
	queue<int> q;
	q.push(u);
	distnode[u]=0;
	while(!q.empty())
	{
		tmp = q.front();
		q.pop();
		visit[tmp]=1;

		if(distnode[tmp]>max_dist)
		{
			max_dist=distnode[tmp];
			farthestnode = tmp;
		}
		for(int i=0;i<graph[tmp].size();i++)
		{
			next_node = graph[tmp][i];
			if(!visit[next_node])
			{
				distnode[next_node]=distnode[tmp]+distnce[tmp][next_node];
				q.push(next_node);
			}
		}

	}

}


int main()
{
	string s,s1;
	int from,dest,cost;
	stringstream ss;

	while(!cin.eof())
	{
		getline(cin,s);

		if(s=="")
		{
			cout<<0<<"\n";
			continue;
		}

		FOR(i,SZ)
		graph[i].clear();

		memset(distnce,0,sizeof(distnce));
		memset(distnode,0,sizeof(distnode));

		while(!cin.eof() && s.size()>0)
		{
			if(s=="")
			break;
			ss.clear();
			ss<<s;
			ss>>from>>dest>>cost;

			graph[from].push_back(dest);
			graph[dest].push_back(from);

			distnce[from][dest]=cost;
			distnce[dest][from]=cost;

			getline(cin,s);
		}

		bfs(1);
		bfs(farthestnode);

		cout<<max_dist<<"\n";

	}

	return 0;

}

100

101

102

103

104

105

106

107

#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 bfs(int u)

{

int tmp;

memset(visit,0,sizeof(visit));

int next_node;

max_dist=0;

queue<int> q;

q.push(u);

distnode[u]=0;

while(!q.empty())

{

tmp = q.front();

q.pop();

visit[tmp]=1;

if(distnode[tmp]>max_dist)

{

max_dist=distnode[tmp];

farthestnode = tmp;

}

for(int i=0;i<graph[tmp].size();i++)

{

next_node = graph[tmp][i];

if(!visit[next_node])

{

distnode[next_node]=distnode[tmp]+distnce[tmp][next_node];

q.push(next_node);

}

int main()

{

string s,s1;

int from,dest,cost;

stringstream ss;

while(!cin.eof())

{

getline(cin,s);

if(s=="")

{

cout<<0<<"\n";

continue;

}

FOR(i,SZ)

graph[i].clear();

memset(distnce,0,sizeof(distnce));

memset(distnode,0,sizeof(distnode));

while(!cin.eof() && s.size()>0)

{

if(s=="")

break;

ss.clear();

ss<<s;

ss>>from>>dest>>cost;

graph[from].push_back(dest);

graph[dest].push_back(from);

distnce[from][dest]=cost;

distnce[dest][from]=cost;

getline(cin,s);

}

bfs(1);

bfs(farthestnode);

cout<<max_dist<<"\n";

}

return 0;

}

11709

Asif NaeemNovember 16, 2014

#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)
		break;
		mp.clear();
		getchar();



		for(int i=0;i<p;i++)
		{
			getline(cin,s);
			mp[s]=i;
			graph[i].clear();
		}

		for(int i=0;i<t;i++)
		{
			getline(cin,s);
			getline(cin,s1);
			graph[mp[s]].push_back(mp[s1]);

		}
		memset(visited,0,sizeof(visited));

		for(int i=0;i<p;i++)
			dfs(i,i);

		memset(visit,0,sizeof(visit));
		int cnt=0;
		for(int i=0;i<p;i++)
		{
			if(!visit[i])
			{
				cnt++;
				for(int j=i+1;j<p;j++)
				{
					if(!visit[j] && visited[i][j] && visited[j][i])
					{
						visit[j]=1;
					}
				}
			}
		}
		cout<<cnt<<"\n";
	}

	return 0;

}

#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)

break;

mp.clear();

getchar();

for(int i=0;i<p;i++)

{

getline(cin,s);

mp[s]=i;

graph[i].clear();

}

for(int i=0;i<t;i++)

{

getline(cin,s);

getline(cin,s1);

graph[mp[s]].push_back(mp[s1]);

}

memset(visited,0,sizeof(visited));

for(int i=0;i<p;i++)

dfs(i,i);

memset(visit,0,sizeof(visit));

int cnt=0;

for(int i=0;i<p;i++)

{

if(!visit[i])

{

cnt++;

for(int j=i+1;j<p;j++)

{

if(!visit[j] && visited[i][j] && visited[j][i])

{

visit[j]=1;

}

cout<<cnt<<"\n";

}

return 0;

}

341

Asif NaeemSeptember 16, 2014

#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]);
        find_path(NExt[i][j],j);
    }
}
int main()
{
	int NI;
	int intersection;
	int start,end,a,b,c=1;

	while(cin>>NI)
	{
		if(NI==0)
		break;
		first=true;
		for(int i=0;i<11;i++)
		{
			for(int j=0;j<11;j++)
			{
				path[i][j]=inf;
				NExt[i][j]=-1;
			}
		}

		for(int i=1;i<=NI;i++)
		{
			cin>>intersection;

			for(int j=1;j<=intersection;j++)
			{
				cin>>a>>b;
				path[i][a]=b;
			}
		}
		cin>>start>>end;

		for(int i=1;i<=NI;i++)
		{
			for(int j=1;j<=NI;j++)
			{
				for(int k=1;k<=NI;k++)
				{
					if(path[j][i]!=inf && path[i][k]!=inf && (path[j][i]+path[i][k])<=path[j][k])
					{
						path[j][k]=(path[j][i]+path[i][k]);
						NExt[j][k]=i;
					}

				}
			}
		}
		//v.clear();
		cout<<"Case "<<c++<<": Path = ";
		find_path(start,end);

		/*for(int i=v.size()-1;i>=0;i--)
		{
			cout<<v[i];
			if(i)
			cout<<" ";
			else
			cout<<"; ";
		}*/
		cout<<"; "<<path[start][end]<<" second delay\n";
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

#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]);

find_path(NExt[i][j],j);

}

int main()

{

int NI;

int intersection;

int start,end,a,b,c=1;

while(cin>>NI)

{

if(NI==0)

break;

first=true;

for(int i=0;i<11;i++)

{

for(int j=0;j<11;j++)

{

path[i][j]=inf;

NExt[i][j]=-1;

}

for(int i=1;i<=NI;i++)

{

cin>>intersection;

for(int j=1;j<=intersection;j++)

{

cin>>a>>b;

path[i][a]=b;

}

cin>>start>>end;

for(int i=1;i<=NI;i++)

{

for(int j=1;j<=NI;j++)

{

for(int k=1;k<=NI;k++)

{

if(path[j][i]!=inf && path[i][k]!=inf && (path[j][i]+path[i][k])<=path[j][k])

{

path[j][k]=(path[j][i]+path[i][k]);

NExt[j][k]=i;

}

//v.clear();

cout<<"Case "<<c++<<": Path = ";

find_path(start,end);

/*for(int i=v.size()-1;i>=0;i--)

{

cout<<v[i];

if(i)

cout<<" ";

else

cout<<"; ";

}*/

cout<<"; "<<path[start][end]<<" second delay\n";

}

return 0;

}

This problem can also be solved using Dijkstra’s algorithm. The one thing to keep in mind is to store the parent vertex of any vertex, so that we can reconstruct the path once we reached the target node. To remember the path, we can use a vector to store where I con from in some

Continue Reading “341” →

Category: Graph Algorithm

11015

208

459

10308

11709

341

Archives

Categories